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

jong_p·2021년 11월 21일
0

영혼의 알고리즘

목록 보기
2/19

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인 '나'를 가지고 노드를 만든다. 이 때 왼쪽과 오른쪽에 각각 서브트리가 생긴다.
이 서브트리도 똑같은 메소드로 재귀적으로 트리를 빌드한다.

profile
알고리즘 정리 좀 해볼라고

0개의 댓글