2023.10.17 Today's Challenge

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

Validate Binary Tree Nodes - LeetCode

트리니까 보통의 방법인 BFS/DFS 로 풀면 됨

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        def find_root():
            children = set(leftChild) | set(rightChild)
            for i in range(n):
                if i not in children:
                    return i
            return -1
        
        root = find_root()
        if root == -1:
            return False
        
        seen = {root}
        stack = [root]
        while stack:
            node = stack.pop()
            for child in [leftChild[node], rightChild[node]]:
                if child != -1:
                    if child in seen:
                        return False
                    stack.append(child)
                    seen.add(child)
        
        return len(seen) == n