leetcode medium : Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal - LeetCode

Construct Binary Tree from Inorder and Postorder Traversal - LeetCode

inorder : left root right
postorder : left right root

postorder의 마지막요소는 root node라는 것을 이용하면 쉽게 풀 수 있다.

 

recursive 하게, memory 많이 쓰고, linear하게 구현하면 진짜 쉽게 구현할 수 있다. 다음은 그렇게 구현한 다른 사람의 코드

class Solution:
    def buildTree(self, inorder, postorder):
        if not inorder or not postorder:
            return None
        
        root = TreeNode(postorder.pop())
        inorderIndex = inorder.index(root.val) # Line A

        root.right = self.buildTree(inorder[inorderIndex+1:], postorder) # Line B
        root.left = self.buildTree(inorder[:inorderIndex], postorder) # Line C

        return root

근데 이렇게하면 시간복잡도랑 공간복잡도가 O(N log N) 정도 나올거같다.

 

나는 iterative solution으로 구현했다.

# 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, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        ii = dict()
        for i in range(len(inorder)):
            ii[inorder[i]] = i
        
        root = TreeNode()
        stack = [(root, 0, len(inorder) - 1, 0, len(postorder) - 1)]
        
        while stack:
            node, i_low, i_high, p_low, p_high = stack.pop()
            
            node.val = postorder[p_high]
            
            index = ii[postorder[p_high]]
            
            left_count = index - i_low
            right_count = i_high - index
            
            if left_count:
                node.left = TreeNode()
                stack.append((node.left, i_low, index - 1, p_low, p_low + left_count - 1) )
                
            if right_count:
                node.right = TreeNode()
                stack.append((node.right, index + 1, i_high, p_low + left_count, p_high - 1))
                
        
        return root

 

역시 구현은 좀 복잡하지만 성능은 확실..

 

다른 사람 코드 보니까 recursive solution으로도 충분히 심플하고 효율적으로 구현할 수 있다.

class Solution:
    def buildTree(self, inorder, postorder):
        map_inorder = {}
        for i, val in enumerate(inorder): map_inorder[val] = i
        def recur(low, high):
            if low > high: return None
            x = TreeNode(postorder.pop())
            mid = map_inorder[x.val]
            x.right = recur(mid+1, high)
            x.left = recur(low, mid-1)
            return x
        return recur(0, len(inorder)-1)