Medium
题目描述
你有 n 个二叉树的节点，节点编号从 0 到 n - 1，其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]，如果给定的所有节点恰好组成一个有效的二叉树，则返回 true，否则返回 false。
如果节点 i 没有左子节点，那么 leftChild[i] 就等于 -1。对于右子节点也是如此。
注意：节点没有值，在这个问题中我们只使用节点编号。
示例 1：
输入: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
输出: true
示例 2：
输入: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
输出: false
示例 3：
输入: n = 2, leftChild = [1,0], rightChild = [-1,-1]
输出: false
提示：
n == leftChild.length == rightChild.length1 <= n <= 10^4-1 <= leftChild[i], rightChild[i] <= n - 1
解题思路
这道题需要验证给定的节点能否构成一个有效的二叉树。一个有效的二叉树必须满足以下条件：
- 唯一根节点：有且仅有一个节点没有父节点（即根节点）
- 无重复父子关系：每个节点最多只能有一个父节点
- 连通性：所有节点都必须连通，即能通过根节点访问到所有节点
- 无环：不能存在环路
解题思路：
首先统计每个节点的入度（有多少个父节点指向它）。在有效的二叉树中，根节点入度为0，其他节点入度为1。
然后从根节点开始进行DFS或BFS遍历，检查是否能访问到所有n个节点。如果访问的节点数量等于n，说明所有节点都连通；否则存在孤立的节点或环路。
主要检查点：
- 入度为0的节点数量必须为1（唯一根节点）
- 入度大于1的节点不能存在（违反树的性质）
- 从根节点能访问到所有节点（连通性）
这种方法时间复杂度为O(n)，空间复杂度为O(n)，是最优解法。
代码实现
class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
vector<int> indegree(n, 0);
// 计算每个节点的入度
for (int i = 0; i < n; i++) {
if (leftChild[i] != -1) {
indegree[leftChild[i]]++;
if (indegree[leftChild[i]] > 1) return false; // 一个节点不能有多个父节点
}
if (rightChild[i] != -1) {
indegree[rightChild[i]]++;
if (indegree[rightChild[i]] > 1) return false; // 一个节点不能有多个父节点
}
}
// 找到根节点（入度为0）
int root = -1;
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
if (root != -1) return false; // 不能有多个根节点
root = i;
}
}
if (root == -1) return false; // 必须有一个根节点
// 从根节点开始DFS，检查是否能访问所有节点
vector<bool> visited(n, false);
function<void(int)> dfs = [&](int node) {
if (node == -1 || visited[node]) return;
visited[node] = true;
dfs(leftChild[node]);
dfs(rightChild[node]);
};
dfs(root);
// 检查是否所有节点都被访问
for (int i = 0; i < n; i++) {
if (!visited[i]) return false;
}
return true;
}
};
class Solution:
def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
indegree = [0] * n
# 计算每个节点的入度
for i in range(n):
if leftChild[i] != -1:
indegree[leftChild[i]] += 1
if indegree[leftChild[i]] > 1: # 一个节点不能有多个父节点
return False
if rightChild[i] != -1:
indegree[rightChild[i]] += 1
if indegree[rightChild[i]] > 1: # 一个节点不能有多个父节点
return False
# 找到根节点（入度为0）
root = -1
for i in range(n):
if indegree[i] == 0:
if root != -1: # 不能有多个根节点
return False
root = i
if root == -1: # 必须有一个根节点
return False
# 从根节点开始DFS，检查是否能访问所有节点
visited = [False] * n
def dfs(node):
if node == -1 or visited[node]:
return
visited[node] = True
dfs(leftChild[node])
dfs(rightChild[node])
dfs(root)
# 检查是否所有节点都被访问
return all(visited)
public class Solution {
public bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
int[] indegree = new int[n];
// 计算每个节点的入度
for (int i = 0; i < n; i++) {
if (leftChild[i] != -1) {
indegree[leftChild[i]]++;
if (indegree[leftChild[i]] > 1) return false; // 一个节点不能有多个父节点
}
if (rightChild[i] != -1) {
indegree[rightChild[i]]++;
if (indegree[rightChild[i]] > 1) return false; // 一个节点不能有多个父节点
}
}
// 找到根节点（入度为0）
int root = -1;
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
if (root != -1) return false; // 不能有多个根节点
root = i;
}
}
if (root == -1) return false; // 必须有一个根节点
// 从根节点开始DFS，检查是否能访问所有节点
bool[] visited = new bool[n];
void DFS(int node) {
if (node == -1 || visited[node]) return;
visited[node] = true;
DFS(leftChild[node]);
DFS(rightChild[node]);
}
DFS(root);
// 检查是否所有节点都被访问
for (int i = 0; i < n; i++) {
if (!visited[i]) return false;
}
return true;
}
}
var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
const indegree = new Array(n).fill(0);
// 计算每个节点的入度
for (let i = 0; i < n; i++) {
if (leftChild[i] !== -1) {
indegree[leftChild[i]]++;
if (indegree[leftChild[i]] > 1) return false; // 一个节点不能有多个父节点
}
if (rightChild[i] !== -1) {
indegree[rightChild[i]]++;
if (indegree[rightChild[i]] > 1) return false; // 一个节点不能有多个父节点
}
}
// 找到根节点（入度为0）
let root = -1;
for (let i = 0; i < n; i++) {
if (indegree[i]
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 需要遍历所有节点计算入度，然后进行一次DFS遍历 |
| 空间复杂度 | O(n) | 需要额外的入度数组、访问标记数组，以及递归调用栈空间 |