1361. Validate Binary Tree Nodes

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.

class Solution {
    int dfs(int u, vector<int>& l, vector<int>& r) {
        int res = 1;
        if(l[u] != -1) res += dfs(l[u], l, r);
        if(r[u] != -1) res += dfs(r[u], l, r);
        return res;
    }
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        int par[10001];
        memset(par, -1, sizeof par);
        for(int i = 0; i < n; i++) {
            int l = leftChild[i], r = rightChild[i];
            if(l != -1 and par[l] != -1) return false;  //more then two parent
            if(r != -1 and par[r] != -1) return false;
            if(l != -1) par[l] = i;
            if(r != -1) par[r] = i;
        }
        int root = -1;
        for(int i = 0; i < n and root == -1; i++) {
            if (par[i] == -1) root = i;
        }
        if(root == -1) return false;    //cycle

        return dfs(root, leftChild, rightChild) == n;   // only one tree
    }
};