[LeetCode] 1361. Validate Binary Tree Nodes

 

https://leetcode.com/problems/validate-binary-tree-nodes/description/

Validate Binary Tree Nodes - LeetCode

문제 유형 : BFS / DFS

문제 난이도 : Medium

 

문제

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.

 

n개의 노드가 있다. leftChild와 rightChild배열의 i번째 주소에는 각각 i번째 노드의 왼쪽 자식과 오른쪽 자식이 있다.

정확히 하나의 유효한 이진 트리가 있으면true를 반환하라.

leftChild와 rightChild의 값이 -1이면, 각각 왼쪽, 오른쪽 자식이 없다는 뜻이다.

 

따로 값은 없고, 노드의 번호만 사용합니다.(0~n-번까지)

 

풀이

leftChild와 rightChild를 하나씩 순회하면서, 노드들의 연결 정보를 만든다.

연결 정보를 만들면서, 연결되는 노드의 진입차수를 따로 저장한다.

 

노드의 진입차수가 0인 노드(루트)부터 BFS를 시작한다.

만약 BFS 도중에, 이미 만난 노드가 있다면, false를 반환한다.

 

순회를 끝내고, 하나라도 방문하지 않은 노드가 있으면 false를 반환한다.

 

코드

C++

 

 

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        vector<vector<int>> graph(n, vector<int>());
        vector<int> indegree(n, 0);

        for(int i = 0; i < n; i++) {
            if(leftChild[i] != -1) {
                graph[i].push_back(leftChild[i]);
                indegree[leftChild[i]]++;
            }
            if(rightChild[i] != -1) {
                graph[i].push_back(rightChild[i]);
                indegree[rightChild[i]]++;
            }
        }

        queue<int> q;
        vector<int> visited(n, false);

        int startIdx = distance(indegree.begin(), min_element(indegree.begin(), indegree.end()));
        q.push(startIdx);
        visited[startIdx] = true;

        while(!q.empty()) {
            const auto curr = q.front();
            q.pop();

            for(const auto& next : graph[curr]) {
                if(visited[next]) {
                    return false;
                } else {
                    visited[next] = true;
                    q.push(next);
                }
            }
        }

        bool isOnlyBinary = true;
        for(const auto& v : visited) {
            isOnlyBinary &= v;
            cout << v << endl;
        }

        return isOnlyBinary;
    }
};