【LeetCode第 177 场周赛】5170. 验证二叉树
考场上没有完成这道题
二叉树上有 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
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/validate-binary-tree-nodes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
图论这个看着真厉害
不过我不懂没有学科基础知识。。。凉凉
利用图论的知识,-1的个数等于结点个数加1时为二叉树
class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& l, vector<int>& r) {
int count = 0;
for(int i=0;i<n;i++){
if(l[i]==-1) count ++;
if(r[i]==-1) count ++;
}
return count==n+1;
}
};
作者：sinclairwang
链接：https://leetcode-cn.com/problems/validate-binary-tree-nodes/solution/li-yong-tu-lun-de-zhi-shi-zhi-jie-tong-ji-1de-ge-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。思路： 满足无环连通图，即为树。 若要满足无环图，遍历过程中不能出现重复结点。 若要满足连通图，遍历完成后经过的顶点数需为n个 至于为什么是二叉树不是三叉树四叉树，因为两个子节点数组可以看作一个邻接表，每个结点的邻居数可能为2、1、0，所以，如果它是树，一定是二叉树。
作者：ni-jin-tian-zhen-hao-kan-2 链接：https://leetcode-cn.com/problems/validate-binary-tree-nodes/solution/ceng-ci-bian-li-yan-du-you-xian-bian-li-man-zu-wu-/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
queue<int> q;
set<int> visd;
int cnt=0,t;
q.push(0);
while(!q.empty()){
t=q.front();q.pop();
if(visd.find(t)!=visd.end())
return false;
visd.insert(t);
cnt++;
if(leftChild[t]!=-1) q.push(leftChild[t]);
if(rightChild[t]!=-1) q.push(rightChild[t]);
}
return cnt==n;
}
};
作者：ni-jin-tian-zhen-hao-kan-2
链接：https://leetcode-cn.com/problems/validate-binary-tree-nodes/solution/ceng-ci-bian-li-yan-du-you-xian-bian-li-man-zu-wu-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。这个懂了，树先把左子树右子树插到队列，等下遍历
然后判断当前节点是否访问过
类似于树的遍历
我可能没有读懂题，导致不知道0节点一定是根节点