LeetCode 105(Construct Binary Tree from Preorder and Inorder Traversal, Python)

1. 문제 링크

• https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

LeetCode - The World's Leading Online Programming Learning Platform

 

2. 문제 설명

• preorder, inorder에 대한 array가 주어졌을 때,
  • 여기서 preorder는 이진트리의 preorder traversal (전위순회)를 의미하고, 
    • 전위순회란 root → left → right 순서로 순회
  • inorder는 같은 트리의 inorder traversal (중위순회)를 의미한다. 
    • 중위순회란 left → root → right 순서로 순회
• 이 때 이진트리를 만들어서 반환
• 예시) 아래의 preorder, inorder array가 주어졌을 때,
  • preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
  • 이는 아래의 binary tree에 대한 순회이고, 
    • 이에 [3,9,20,null,null,15,7]의 root를 반환하면 된다.

 

3. 처음 풀이

• preorder 순회는 root → left → right로, inorder 순회는 left → root → right로 돌기 때문에,
  • preorder의 가장 첫번째 값이 root.val이 되며,
  • inorder의 left는 list의 root.val의 왼쪽, right는 root.val을 기준으로 오른쪽 list가 된다. 
  • 위의 예시로 봤을 때, 
    • preorder의 가장 첫번째 값인 3이 root이며, 
    • inorder가 [9,3,15,20,7]이므로, 3을 기점으로 왼쪽인 [9]가 3의 왼쪽 subtree이고, 오른쪽인 [15,20,7]이 오른쪽 subtree임을 알 수 있다. 
  • 결과적으로 TreeNode(val, leftsubtree, rightsubtree)를 반환하는 재귀함수를 아래와 같이 작성하였다. 
    • leftsubtree에는 left_inorder_list, left_preorder_list를 인자로 받는 buildTree함수를 넣고,
      
      • 여기서, preorder의 경우, 0번째 element는 root이므로 1번째부터 left list 길이만큼 slicing 하면 된다.
    • rightsubtree에는 right_inorder_list, right_preorder_list를 인자로 받는 buildTree함수를 넣었다.
      • 여기서 preorder의 경우, 1+left list 길이 부터 slicing하면 된다. 
  • runtime의 경우, 60% 정도 나왔는데, 
  • 아래 그래프를 보면 뭔가 좀 더 개선할 수 있는 다른 방법이 있는 것 같아보였다. 

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        
        if len(preorder) == 0:
            return None
                
        if len(preorder) == 1:
            return TreeNode(preorder[0])

        val = preorder[0]
        idx=inorder.index(val)
        left_len=len(inorder[:idx])

        left_inorder_list = inorder[:idx]
        left_preorder_list = preorder[1:left_len+1]

        right_inorder_list = inorder[idx+1:]
        right_preorder_list = preorder[left_len+1:]

        return TreeNode(val, self.buildTree(left_preorder_list,left_inorder_list), self.buildTree(right_preorder_list,right_inorder_list))

 

4. 다른 풀이

• runtime 상위에 있던 다른 풀이 
  • inorder에 대한 index를 key로 하고 element를 value로 하는 dict을 만들어놓고, 
  • dfs라는 함수를 만들어서,
    • root에는 preorder의 첫번째 값을 넣으면서 pop을 시키고 (root = TreeNode(preorder.pop(0))
    • root.left는 dfs(l,idx-1), root.right는 dfs(idx+1,r)를 한 후 root를 반환한다.
  • 여기서 위의 기존 풀이와 runtime이 차이가 나는 부분은 index를 사용하는 방식이다. 
    • 기존에는 index지점을 잡아서 slicing을 하고 새로운 list를 만드는데, 이는 runtime을 증가시키게 된다.
    • 아래 풀이의 경우, hash table같은 방식으로, 각 value에 대한 index를 dictionary에 저장을 해두기 때문에, index를 찾는 반복적인 과정을 없애고 있어서, 더 효율적인 것!

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        inorderIdx = {v:i for i, v in enumerate(inorder)}
        def dfs(l, r):
            if l > r:
                return None
            root = TreeNode(preorder.pop(0))
            idx = inorderIdx[root.val]
            root.left = dfs(l,idx-1)
            root.right = dfs(idx+1, r)
            return root

        return dfs(0, len(inorder)-1)

 

5. 배운 점 

• list slicing은 large dataset에서는 긴 연산이다. 
• 매번 slicing하기보다, hash table을 사용하면 runtime이 더 효율적.