[LeetCode] #106. Construct Binary Tree from Inorder and Postorder Traversal [트리/해쉬/분할정복/파이썬/python]

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

Construct Binary Tree from Inorder and Postorder Traversal - LeetCode

전위순회(inorder traversal)와 후위순회(postorder traversal)에 대한 개념을 아는지,

그것을 활용하여 재귀를 통해 binary tree를 출력하는 문제다. 

 

inorder 순회는 : left서브트리->root->right서브트리

postorder 순회는 : left서브트리->right서브트리->root 

(+) preorder 순회는: root->left서브트리->right서브트리

순서로 트리순회하는 방식이다. 

 

이것을 활용하여 inorder순회의 root 인덱스를 정보로 받아서

그것에 맞는 postorder순회의 인덱스를 해싱해서 

재귀로 트리를 build하는 buildTree()하면 된다. 

 

예제)

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

디버깅을 해보면 첫번째 호출에서

left_inorder는 [9], right_inorder는 [15,20,7]

left_postorder는 [9], right_postorder는 [15,7,20]이다.

root인 3을 기준으로 분할한 것..! (divide and conquer)

 

그리고 해당 정보로 재귀하면서 binary tree build를 하면 된다. 

 

파이썬 코드

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if not inorder:
            return None
        head = TreeNode(val=postorder[-1])
        inorder_root=inorder.index(head.val)
        left_inorder=inorder[:inorder_root]
        right_inorder=inorder[inorder_root+1:]
       
        left_postorder=postorder[:inorder_root]
        right_postorder=postorder[inorder_root:-1]

        head.left = self.buildTree(left_inorder, left_postorder)
        head.right = self.buildTree(right_inorder, right_postorder)
        
        return head

 

비슷한 개념 (전위/중위/후위순회) 문제

https://www.acmicpc.net/problem/1991