[LeetCode] 1361.Validate Binary Tree Nodes

[LeetCode] 1361.Validate Binary Tree Nodes

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

풀이

• 하나의 Binary Tree가 되기 위한 조건:
  (1) 루트 노드(parent가 없는 노드)가 하나만 있어야 한다
  (2) 루트 노드를 제외한 모든 노드는 parent 노드를 하나만 가져야 한다
  (3) 자식-부모 관계에서 사이클이 형성되어선 안된다

• 주의해야 할 테스트케이스들

  Input: n=4, leftChild=[1, 0, 3, -1], rightChild=[-1,-1,-1,-1]
  Answer: false

  Input: n=4, leftChild=[1, 2, 0, -1], rightChild=[-1,-1,-1,-1]
  Answer: false

  Input: n=1, leftChild=[-1], rightChild=[-1]
  Answer: true

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

• 문제를 읽자마자 cycle 유무를 확인해야할 것 같다는 느낌이 왔지만, 귀찮아서 사이클 처리를 생략했다.
  여러 번의 틀린 코드 제출 끝에, 결국 사이클 처리를 하도록 코드를 처음부터 다시 짰다.
  빨리 풀려고 꼼수 부리는 것보다, 처음부터 천천히 제대로된 로직을 짜야는 것이 오히려 시간이 절약된다.

#include <iostream>

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
    	//parent[i]: i번 노드의 parent 노드 번호
        vector<int> parent = vector<int>(n, -1);
        
        for(int i = 0; i<n; ++i){
            //left
            int child = leftChild[i];
            if(child != -1){
                //(2)check if two parents
                if(parent[child] != -1) return false;
                
                int p = i;
                parent[child] = p;
                while(parent[p] != -1){
                    //(3)check if cycle
                    if(p == child) return false;
                    parent[child] = parent[p];
                    p = parent[p];
                }
            }

            //right
            child = rightChild[i];
            if(child != -1){
                //(2)check if two parents
                if(parent[child] != -1) return false;

                int p = i;
                parent[child] = p;
                while(parent[p] != -1){
                    //(3)check if cycle
                    if(p == child) return false;
                    parent[child] = parent[p];
                    p = parent[p];
                }
            }
        }

        bool foundRoot = false;
        for(int i = 0; i<n; ++i){
            if(parent[i]== -1){
                //(1)check if two root nodes
                if(foundRoot) return false;
                else foundRoot = true;
            }
        }
		
        //(1)check if no root node 
        return foundRoot;
    }
};