You have n
binary tree nodes numbered from 0
to n - 1
where node i
has two children leftChild[i]
and rightChild[i]
, return true
if and only if all the given nodes form exactly one valid binary tree.
If node i
has no left child then leftChild[i]
will equal -1
, similarly for the right child.
Note that the nodes have no values and that we only use the node numbers in this problem.
Example 1:
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true
Example 2:
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false
Example 3:
Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false
Constraints:
n == leftChild.length == rightChild.length
1 <= n <= 104
-1 <= leftChild[i], rightChild[i] <= n - 1
这道题说是给了两个数组 leftChild 和 rightChild,其中 leftChild[i] 表示结点i的左子结点,rightChild[i] 表示结点i的右子结点,若值为 -1,表示没有左子结点或着右子结点,问给定的数组是否可以组成一个有效的二叉树。对于二叉树想必大家都不陌生,来看一下题目中给的例子,例子1是一棵有效的二叉树,例子2中由于结点3有两个父结点,所以不是有效的二叉树,例子3中两个结点互为父结点了,这也不是有效的二叉树。二叉树是一种特殊的有向图,一棵有效的二叉树至少要具备这个几个特点,首先是只有一个根结点,即所有结点必须是连成一个整体的,其次是每个结点最多有两个子结点,然后每个结点最多只有一个父结点,最后就是不能出现环。
有向图有个入度 In Degree 的概念,就是某个结点被其他结点连通的个数,对于有效二叉树来说,除了根结点之外的每个结点的入度必须是1,即每个结点最多只有一个父结点,根结点的入度是0,其没有父结点。那这里就可以通过计算每个结点的入度,来快速去除一些无效的二叉树,这里用个长度为n的入度数组 inDegree,然后遍历两个数组,若左子结点不为 -1,则将其入度值自增1,此时判断一下,若入度值大于1了,说明是无效的二叉树,返回 false,对右子结点进行相同的处理。
仅判断结点的入度值是不够的,比如例子3中,每个结点的入度都是1,但不是有效二叉树,因为其没有根结点,所以接下来需要找出根结点,而且只能有一个根结点,就是说只能有一个结点的入度是0,若找到了多个,则返回 false。找到了根结点后也还不能说就是有效的二叉函数了,还得保证所有的结点都是相连的,这个通过从根结点开始遍历二叉树,统计遍历到的结点个数,若成功遍历了n个结点,才能说是有效的二叉树。遍历的方法可以用 BFS 或者 DFS,这里先用 BFS,使用队列 queue 来辅助运算,先把根结点 root 放进去,然后进行 while 循环,每次从 queue 中取出一个结点,计数器 cnt 自增1,然后看其左右子结点,若存在就加入到队列中继续循环,最后判断 cnt 是否等于n即可,参见代码如下:
解法一:
class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
int root = -1, cnt = 0;
vector<int> inDegree(n);
for (int i = 0; i < n; ++i) {
int left = leftChild[i], right = rightChild[i];
if (left != -1 && ++inDegree[left] > 1) return false;
if (right != -1 && ++inDegree[right] > 1) return false;
}
for (int i = 0; i < n; ++i) {
if (inDegree[i] != 0) continue;
if (root != -1) return false;
root = i;
}
if (root == -1) return false;
queue<int> q{{root}};
while (!q.empty()) {
auto t = q.front(); q.pop();
++cnt;
if (leftChild[t] != -1) q.push(leftChild[t]);
if (rightChild[t] != -1) q.push(rightChild[t]);
}
return cnt == n;
}
};
下面解法是用 DFS 来遍历二叉树,写起来更加简洁一些,在递归函数中首先判断若当前结点 node 为 -1,说明不存在,则返回0,否则分别对其左右子结点调用递归函数,将返回值加起来,再加上1,就是以当前结点 node 为根结点的二叉树的结点个数了,参见代码如下:
解法二:
class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
int root = -1, cnt = 0;
vector<int> inDegree(n);
for (int i = 0; i < n; ++i) {
int left = leftChild[i], right = rightChild[i];
if (left != -1 && ++inDegree[left] > 1) return false;
if (right != -1 && ++inDegree[right] > 1) return false;
}
for (int i = 0; i < n; ++i) {
if (inDegree[i] != 0) continue;
if (root != -1) return false;
root = i;
}
if (root == -1) return false;
return countNodes(leftChild, rightChild, root) == n;
}
int countNodes(vector<int>& leftChild, vector<int>& rightChild, int node) {
if (node == -1) return 0;
return 1 + countNodes(leftChild, rightChild, leftChild[node]) + countNodes(leftChild, rightChild, rightChild[node]);
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1361
参考资料:
https://leetcode.com/problems/validate-binary-tree-nodes/
https://leetcode.com/problems/validate-binary-tree-nodes/solutions/517557/c-find-root-dfs/
LeetCode All in One 题目讲解汇总(持续更新中...)
- LeetCode Validate Binary Nodes 1361leetcode validate binary nodes 节点leetcode nodes pairs leetcode reverse binary levels leetcode maximum binary depth leetcode ancestor common binary leetcode binary add 67 leetcode longest binary zigzag leetcode possible binary trees maximum-width-of-binary-tree leetcode problems unique-binary-search-trees leetcode unique binary