LeetCode 2196 solution

problem

You are given a 2D integer array descriptions where descriptions[i] = [parenti, childi, isLefti] indicates that parenti is the parent of childi in a binary tree of unique values. Furthermore, If isLefti == 1, then childi is the left child of parenti.

If isLefti == 0, then childi is the right child of parenti.

Construct the binary tree described by descriptions and return its root.

The test cases will be generated such that the binary tree is valid.

• Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
• Output: [50,20,80,15,17,19]
• Explanation: The root node is the node with value 50 since it has no parent.
  The resulting binary tree is shown in the diagram.

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
        child = set()
        nodes = {}
        for p,c,left in descriptions:
            if p not in nodes:
                nodes[p] = TreeNode(p)
            if c not in nodes:
                nodes[c] = TreeNode(c)
            if left:
                nodes[p].left = nodes[c]
            else:
                nodes[p].right = nodes[c]
            child.add(c)
        for d in descriptions:
            if d[0] not in child:
                return nodes[d[0]]
        return None

사실 트리는 아직도 어색해서 풀지는 못했고, 해설 중에 가장 깔끔해 보이는 답을 가져왔다. 중요해 보이는 것은 case 세분화를 거치고, if if if else 문을 사용해서 넣어주는 것이다. 바로 넣어주면서 left일 경우에는 hash table [p]의 method인 .left로 넣어주는 것이다. 반대의 경우는 당연하게도 .right로 넣어준다.