[Leetcode] 106. Construct Binary Tree from Inorder and Postorder Traversal

Nov 21

unsolved

106. Construct Binary Tree from Inorder and Postorder Traversal

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Solution

preorder traverse = mid->left->right
inorder traverse = left->mid->right
postorder traverse = left->right->mid

example

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

inorder: 9->3->{15->20->7}
postorder: 9 -> {15->7->20} ->3

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/discuss/1588887/Python-Arriving-at-an-O(N)-solution

code

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if len(postorder)==0:
            return None

        
        val=postorder[-1]
        idx=inorder.index(val)
        
        leftIn=inorder[:idx]
        rigthIn=inorder[idx+1:]
        
        
        leftPo=postorder[:idx]
        rightPo=postorder[idx:-1]
            
        
        return TreeNode(val,self.buildTree(leftIn,leftPo),self.buildTree(rigthIn,rightPo))

preorder: 왼 나 오
postorder:왼 오 나
어떤 한 배열을 받아도, 배열을 세 가지 파트로 나눠서 생각할 수 있음.
우선 root인 '나'를 가지고 노드를 만든다. 이 때 왼쪽과 오른쪽에 각각 서브트리가 생긴다.
이 서브트리도 똑같은 메소드로 재귀적으로 트리를 빌드한다.