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.

 

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

Example 4:

Input: n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1]
Output: false

 

class Solution {

public:

    /*

    single tree: one root:   [one missing value in both of the lists] [otherwise false]

    single parent:    [If same value repeated ]

    no cycle:   [all the values appear means cycle]

    

    */

    

    

    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {

        if (leftChild.size() != rightChild.size()) {

            return false;

        }

        vector<bool> dp(n, true);

        for (auto val : leftChild) {

            if (val != -1) {

                if (!dp[val]) {

                    return false;

                }

                dp[val] = false;

            }

        }

        for (auto val : rightChild) {

            if (val != -1) {

                if (!dp[val]) {

                    return false;

                }

                dp[val] = false;

            }

        }

        int root = -1;

        int count = 0;

        for (int i = 0; i < dp.size(); i++) {

            bool val = dp[i];

            if (val) {

                root = i;

                count++;

            }

        }

        if (count != 1) {

            return false;

        }

        if (!dfs(n, leftChild, rightChild, root)) {

            return false;

        }

        return true;

    }

    

    bool helper(int root, vector<int>& leftChild, vector<int>& rightChild,

                vector<int>& visited) {

        if (visited[root] == 1) {

            return false;

        }

        if (visited[root] == 2) {

            return true;

        }

        visited[root] = 1;

        if (leftChild[root] != -1) {

            if (!helper(leftChild[root], leftChild, rightChild, visited)) {

                return false;

            }

        }

        if (rightChild[root] != -1) {

            if (!helper(rightChild[root], leftChild, rightChild, visited)) {

                return false;

            }

        }

        visited[root] = 2;

        return true;

    }

    

    bool dfs(int n, vector<int>& leftChild, vector<int>& rightChild, int root) {

        vector<int> visited(n, 0);

        if (!helper(root, leftChild, rightChild, visited)) {

            return false;

        }

        for (auto val: visited) {

            if (val == 0) {

                return false;

            }

        }

        return true;

    }

};