106. Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

 

# 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]:
        # inorder: 왼, 중, 오
        # postoder: 왼, 오, 중
        # inorder 의 첫번째는 가장 왼쪽 노드
        # postorder의 첫번째도 가장 왼쪽 노드
        # postorder의 가장 오른쪽은 root 노드
        # 그래서 root 노드 보다 inorder의 인덱스가 오른쪽에 있으면, root의 오른쪽에 있는 것임
        # postorder의 두번째 오른쪽은 root의 오른쪽 자식
        if not inorder or not postorder: # 둘다 비었으면
            return None

        root = TreeNode(postorder[-1])
        # inorder에서 루트노드의 index 찾기
        mid = inorder.index(postorder[-1]) 
        print(inorder, postorder, 'root: ', postorder[-1], 'idx: ', mid)
        # 루트 노드 제외해서 전달해야 함
        root.left = self.buildTree(inorder[:mid], postorder[:mid]) 
        # postorder의 right는 inorder에서 mid(root)의 index 포함해서 넘겨야 함
        root.right = self.buildTree(inorder[mid+1:], postorder[mid:-1]) 

        return root

 

맞췄지만, 느림

 

https://youtu.be/vm63HuIU7kw?si=KZW6uqnHtIRa_BSy

 

# 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]:
        # inorder: 왼, 중, 오
        # postoder: 왼, 오, 중
        # inorder 의 첫번째는 가장 왼쪽 노드
        # postorder의 첫번째도 가장 왼쪽 노드
        # postorder의 가장 오른쪽은 root 노드
        # 그래서 root 노드 보다 inorder의 인덱스가 오른쪽에 있으면, root의 오른쪽에 있는 것임
        # postorder의 두번째 오른쪽은 root의 오른쪽 자식
        ######################3
        # 그래서, 오른쪽 노드를 먼저 만드는 방식으로 구현..

        if not inorder:
            return None
        
        root = TreeNode(postorder.pop())
        idx = inorder.index(root.val)
        
        # postorder.pop() 했기때문에, root 노드는 삭제되었음. 
        # 따라서, postorder 넘겨줄때 idx 로 인덱싱 필요 X
        root.right = self.buildTree(inorder[idx+1:], postorder)

        # inorder 에 idx 제외
        root.left = self.buildTree(inorder[:idx], postorder)
        return root

 

postorder를 슬라이싱하지 않는 이유

1. postorder의 마지막 원소가 항상 현재 서브트리의 루트 노드:
   • postorder 순회 방식은 왼쪽 → 오른쪽 → 루트입니다.
   • 따라서 postorder.pop()을 호출하면 항상 현재 서브트리의 루트 노드를 가져옵니다.
     • postorder.pop() 했기때문에, root 노드는 삭제되었음. 
     • 따라서, postorder 넘겨줄때 idx 로 인덱싱 필요 X
   • 이를 통해 추가적인 슬라이싱 없이 postorder를 효율적으로 처리할 수 있습니다.
2. postorder는 한 방향으로 줄어들며, 서브트리의 순서를 유지:
   • 루트 노드를 처리하고 나면, 남은 postorder에서 오른쪽 서브트리 → 왼쪽 서브트리 순서로 처리됩니다.
   • 이를 이용해 슬라이싱 없이 postorder 리스트를 재사용할 수 있습니다.
3. 슬라이싱의 비효율성 회피:
   • 리스트를 슬라이싱하면 새로운 리스트가 만들어지므로 시간과 공간이 추가로 필요합니다.
   • 대신 pop()으로 리스트를 줄여가며 재귀적으로 처리하면 메모리 사용량을 최소화할 수 있습니다.

---

inorder는 왜 슬라이싱이 필요한가?

inorder 리스트는 슬라이싱을 통해 현재 서브트리의 왼쪽 및 오른쪽 부분을 나눠야 합니다. 이유는:

1. inorder에서 루트 노드의 위치가 서브트리 경계를 결정:
   • inorder.index(root.val)을 통해 현재 루트 노드의 위치(idx)를 찾습니다.
   • inorder[:idx]: 루트 노드의 왼쪽 서브트리.
   • inorder[idx+1:]: 루트 노드의 오른쪽 서브트리.
2. 각 서브트리에 대해 새로운 경계를 전달해야 함:
   • 재귀 호출마다 inorder 리스트는 왼쪽 또는 오른쪽 서브트리만 포함해야 합니다.
   • 따라서 슬라이싱이 필요합니다.

 

추가 속도 향상: 해쉬맵을 사용하자!!

# 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]:
        # inorder: 왼, 중, 오
        # postoder: 왼, 오, 중
        # inorder 의 첫번째는 가장 왼쪽 노드
        # postorder의 첫번째도 가장 왼쪽 노드
        # postorder의 가장 오른쪽은 root 노드
        # 그래서 root 노드 보다 inorder의 인덱스가 오른쪽에 있으면, root의 오른쪽에 있는 것임
        # postorder의 두번째 오른쪽은 root의 오른쪽 자식
        ######################3
        # 그래서, 오른쪽 노드를 먼저 만드는 방식으로 구현..
        #################################3
        """
        # 속도 빠르게 하기위해, 해쉬맵 사용
        # 인덱스 찾는 부분을, inorder.index() 함수 대신, 해쉬맵으로..
        # 그리고, 로직을 helper 함수로 감싸고.
        # 재귀도. helper 함수로 ..
        """

        inorderIdx = {v:i for i, v in enumerate(inorder)}

        def helper(l, r):
            #if not inorder:
            if l > r: # 순서 역전되면
                return None
            
            root = TreeNode(postorder.pop())
            # idx = inorder.index(root.val)
            idx = inorderIdx[root.val]

            # postorder.pop() 했기때문에, root 노드는 삭제되었음. 
            # 따라서, postorder 넘겨줄때 idx 로 인덱싱 필요 X
            #root.right = self.buildTree(inorder[idx+1:], postorder)
            root.right = helper(idx+1, r)

            # inorder 에 idx 제외
            #root.left = self.buildTree(inorder[:idx], postorder)
            root.left = helper(l, idx-1)
            return root
        
        return helper(0, len(inorder)-1)