Leetcode 1275 Solution

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        std::map<int, std::vector<int>> in_map;
        std::map<int, std::vector<int>> out_map;

        for (int i = 0; i < n; i++)
        {
            int left_child_node = leftChild[i];
            int right_child_node = rightChild[i];

            if (left_child_node != -1)
            {
                in_map[left_child_node].push_back(i);
                out_map[i].push_back(left_child_node);
            }

            if (right_child_node != -1)
            {
                in_map[right_child_node].push_back(i);
                out_map[i].push_back(right_child_node);
            }
        }

        int zero_in_degree_nodes = 0;
        int root_node = -1;
        for (int i = 0; i < n; i++)
        {
            int node_in_degree = in_map[i].size();

            if (node_in_degree == 0)
            {
                zero_in_degree_nodes++;
                root_node = i;
            }

            if (node_in_degree > 1)
                return false;
        }

        if (zero_in_degree_nodes != 1)
            return false;

        std::queue<int> q;
        q.push(root_node);
        int connected_size = 0;

        while (!q.empty())
        {
            int size = q.size();
            for (int i = 0; i < size; i++)
            {
                int node = q.front();
                q.pop();

                connected_size++;

                auto& out_nodes = out_map[node];
                for (auto it = out_nodes.begin(); it != out_nodes.end(); it++)
                    q.push(*it);
            }
        }

        return connected_size == n;
    }
};