LeetCode 1361. 验证二叉树（几种错误、递归建树）

验证二叉树
思路：
① 先由出度、入度求出根节点。
② 然后递归地从根节点出发把所有节点加入unordered_set<int>。
几种错误：

• 根节点不唯一
• 没有根节点
• 某个节点是多个节点的孩子
• 成环。
  前两个问题可由入度数组vector<int> vis解决，后两个问题由unordered_set解决。

class Solution {
public:
    unordered_set<int> nodes;
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        //先找出根节点
        vector<int> vis(n,0);
        for(int i=0;i<n;i++){
            if(leftChild[i]!=-1){
                vis[leftChild[i]]++;
            }  
            if(rightChild[i]!=-1){
                vis[rightChild[i]]++;
            }
        }
        int root = -1;
        for(int i=0;i<n;i++){
            if(vis[i]==0 && root==-1){
                root = i;
            }else if(vis[i]==0 && root!=-1){
                return false;
            }
        }
        if(root==-1){
            return false;
        }
        return dfs(root,leftChild,rightChild) && nodes.size()==n;
    }
    bool dfs(int root, vector<int>& leftChild, vector<int>& rightChild){
        if(nodes.count(root)){
            return false;
        }
        nodes.insert(root);
        if(leftChild[root]!=-1){
            if(!dfs(leftChild[root],leftChild,rightChild)){
                return false;
            }
        }
        if(rightChild[root]!=-1){
            if(!dfs(rightChild[root],leftChild,rightChild)){
                return false;
            }
        }
        return true;
    }
};