LeetCode 2196 Create Binary Tree From Descriptions
리스트로 풀어도 되고, 맵으로 풀어도 된다. 공간 덜 쓰고 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