[Leetcode] 105. Construct Binary Tree from Preorder and Inorder Traversal

문제 바로가기

preorder와 inorder의 탐색 순서 차이를 이용해 해결한다.
preorder[0]는 root 노드 값이므로 해당 값으로 inorder에서 root의 위치를 탐색할 수 있다.
inorder에서 root의 위치를 특정하면 해당 index를 기준으로 left/rightSubtree로 나눌 수 있다.
leftSubtree의 길이는 두 list에서 동일하므로 preorder에서도 left/rightSubtree로 나눌 수 있다.

Time Complexity: $O(n)$
Space Complexity: $O(n)$

# 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]) -> TreeNode:
        inorderHashtable = dict()
        for i, val in enumerate(inorder):
            inorderHashtable[val] = i
            
        def DFS(pFront: int, pRear: int, iFront: int, iRear: int) -> TreeNode:
            if pFront == pRear:
                return None
            
            head = preorder[pFront]
            headIdx = inorderHashtable[head]
            lenL = headIdx - iFront

            leftSubtree = DFS(pFront + 1, pFront + 1 + lenL, iFront, headIdx)
            rightSubtree = DFS(pFront + 1 + lenL, pRear, headIdx + 1, iRear)

            return TreeNode(head, leftSubtree, rightSubtree)
        
        return DFS(0, len(preorder), 0, len(inorder))

최적화

preorder list는 DFS 탐색 순서로 원소를 저장하고 있다는 점을 활용하자.

Time Complexity: $O(n)$
Space Complexity: $O(n)$

# 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 __init__(self):
        self.preorder = None
        self.pIdx = 0
        self.inorderHashtable = dict()
        
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        self.preorder = preorder
        for i, val in enumerate(inorder):
            self.inorderHashtable[val] = i
                
        return self.DFS(0, len(preorder) - 1)
    
    def DFS(self, l: int, r: int) -> TreeNode:
        """
        l: a first index of inorder sublist
        r: a last index of inorder sublist
        """
        if l > r:
            return None
        
        head = self.preorder[self.pIdx]
        headIdx = self.inorderHashtable[head]
        self.pIdx += 1

        return TreeNode(head, self.DFS(l, headIdx - 1), self.DFS(headIdx + 1, r))