LeetCode 2196 Create Binary Tree From Descriptions

접근

  1. map의 key에 node.val, value에 node reference 가 담긴다.
  2. 부모 노드는 p[child] = parent 의 방식으로 저장하여 루트를 찾는다.
  3. descriptions 를 훑으며 map 에 이미 저장된 child 가 있다면 해당 child 를 적절한 left or right 에 연결하고, child 가 map 에 없다면 새로운 노드를 만들어 연결한다.

사고

리스트로 풀어도 되고, 맵으로 풀어도 된다. 공간 덜 쓰고 root 찾는 방법이 있을것도 같다. map 을 안쓰고는 (node 들의 reference 를 다 붙잡고 있지 않고는) tree 만들 방법이 없는거겠지?

 

from collections import deque
from collections import defaultdict
class Solution:
    def createBinaryTree(self, descriptions: list[list[int]]):
        d = dict()
        p = defaultdict(int)

        for parent, child, isLeft in descriptions:
            node = None
            if parent in d:
                node = d[parent]
            else:
                node = TreeNode(val=parent)
                d[parent] = node
            if isLeft:
                if child in d:
                    node.left = d[child]
                else:
                    node.left = TreeNode(val=child)
                    d[child] = node.left
            else:
                if child in d:
                    node.right = d[child]
                else:
                    node.right = TreeNode(val=child)
                    d[child] = node.right

            p[child] = parent

        root = descriptions[0][0]
        while p[root] != 0:
            root = p[root]
        return root