1361. Validate Binary Tree Nodes

• [0, n - 1] 까지의 노드로 구성된 tree가 정상적으로 구성되었는지 확인하는 문제이다.

• 만일 tree가 정상적으로 구성되어있다면 leftChild, rightChild 에 있는 노드 번호의 합은 [0, n - 1] 범위에 있는 노드 중 임의의 숫자 하나가 빠진 숫자의 합이 된다.

• 그리고 여기서 빠진 숫자 = 루트 노드가 되므로 child 노드 번호의 합을 통해서 루트 노드의 번호를 구할 수 있다.
• 그리고 이렇게 구해진 루트 노드 번호가 정상 범위를 초과하는지 확인한다.

• 루트 노드를 기준으로 탐색하면서 모든 노드를 탐색했는지 검사한다.

class Solution {
public:
    bool check(int rootNode, vector<int>& leftChild, vector<int>& rightChild) {
        vector<bool> visited(leftChild.size(), false);
        vector<int> s;
        int count = 0;
        s.push_back(rootNode);
        while (!s.empty()) {
            auto i = s.back();
            s.pop_back();
            if (visited[i]) return false;
            visited[i] = true;
            ++count;
            if (leftChild[i] != -1)
                s.push_back(leftChild[i]);
            if (rightChild[i] != -1)
                s.push_back(rightChild[i]);
        }
        return count == leftChild.size();
    }

    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        if (n == 1) return true;
        int nodeSum = 0;
        for (auto i : leftChild) {
            if (i != -1) nodeSum += i;
        }
        for (auto i : rightChild) {
            if (i != -1) nodeSum += i;
        }
        int expectedSum = (n - 1) * n / 2;
        int rootNode = expectedSum - nodeSum;
        if (rootNode < 0 || rootNode >= n) return false;
        return check(rootNode, leftChild, rightChild);
    }
};