[LeetCode] 889. Construct Binary Tree from Preorder and Postorder Traversal (Python)

Problem

 

Solution

array
binary tree
recursive

 

preorder, postorder list 을 보고 binary tree을 구하는 문제.

 

Code

# 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 constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        post_index = {val: idx for idx, val in enumerate(postorder)}  # Map postorder values to indices
        pre_idx = 0  # Pointer for preorder traversal
        
        def construct(left, right):
            nonlocal pre_idx
            if left > right:  # Base case
                return None
           
            root = TreeNode(preorder[pre_idx])
            pre_idx += 1
            #Leaf node 이면 바로 반환
            if left == right:  # Leaf node condition
                return root
            
            # Find index of the next node in postorder
            #preorder 다음 값이 왼쪽 서브트리의 루트가된다.
            next_val = preorder[pre_idx]
            mid = post_index[next_val] #postorder에서 해당 값의 위치 찾기
            
            # Construct left and right subtrees
            root.left = construct(left, mid)
            root.right = construct(mid + 1, right - 1)
            
            return root
        
        return construct(0, len(postorder) - 1)

 

Complexity

Time Complexity

각 노드를 한 번씩 방문하므로 선형 시간에 실행됨. -> O(N)

 

Space Complexity

최악의 경우(완전한 왼쪽 또는 오른쪽 서브트리) 깊이가 O(n)이 될 수 있음. -> 재귀 호출