题目大意：
验证二叉树
二叉树上有 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
示例 4：
输入：n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1] 输出：false
提示：
- 1 <= n <= 10^4
- leftChild.length == rightChild.length == n
- -1 <= leftChild[i], rightChild[i] <= n – 1
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1361
解题思路分析：
之前文章我多次讲过，遇到树形结构的题目应该首先想到使用dfs或者bfs来解题。本题也不例外。验证有效二叉树的条件有两点，第一，任何节点不能存在两个父节点，反过来说，我们不可能通过两条不同的dfs路径到达同一节点。第二，遍历完二叉树上所有节点后，节点个数应该等于n。如果小于n，说明当前树的根节点并不能联通所有n个节点，属于无效二叉树（比如示例4）。
解题时，我们从根节点0开始dfs深度优先搜索。dfs返回值为当前节点下的节点总数量。另外我们使用一个访问数组来保存已经遍历过的节点。如果你看过我之前对于dfs算法讲解的话（链接在下面），你会记得，dfs二叉树时是不需要使用访问数组的。这里使用访问数组的原因是题目给出的树形结构有可能存在无效二叉树，因此它目的在于判断是否存在多条路线指向同一节点，如果存在，则说明该二叉树无效。
LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(上)
LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(下)
实现代码：
boolean[] visited; // 访问数组
public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
visited = new boolean[n]; // 初始化访问数组
// dfs求解根节点下节点数量，如果数量为n，代表二叉树有效
return dfs(0,leftChild,rightChild)==n;
}
// index为当前节点
// 返回值为当前节点下所有节点数量
int dfs(int index, int[] leftChild, int[] rightChild){
// 如果当前节点已经访问过，说明二叉树无效，返回-1
if(visited[index]) return -1;
// 设置当前节点已访问
visited[index]=true;
// 左子树节点个数
int leftCount=0;
// 如果左子节点不为空
if(leftChild[index]!=-1) {
// dfs左子节点下节点个数
leftCount=dfs(leftChild[index],leftChild,rightChild);
}
// 如果左子树节点个数为-1，说明为无效树，返回-1
if(leftCount==-1) return -1;
// 右子树节点个数
int rightCount=0;
// 如果右子节点不为空
if(rightChild[index]!=-1) {
// dfs右子节点下节点个数
rightCount=dfs(rightChild[index],leftChild,rightChild);
}
// 如果右子树节点个数为-1，说明为无效树，返回-1
if(rightCount==-1) return -1;
// 当前节点下节点个数为：
// 左子树节点个数加上右子树节点个数再加上当前节点
return leftCount+rightCount+1;
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 99.78% of Java online submissions for Validate Binary Tree Nodes.
Memory Usage: 42.9 MB, less than 100.00% of Java online submissions for Validate Binary Tree Nodes.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1361-validate-binary-tree-nodes-解题思路分析/