###### tags: `Leetcode` `medium` `tree` `python`

# 106. Construct Binary Tree from Inorder and Postorder Traversal

## [題目連結:] https://leetcode.com/problems/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.


#### [圖片來源:]https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

## 解題想法:
兄弟題目: [105. Construct Binary Tree from Preorder and Inorder Traversal](/wJVgPFtFTD2MIOuEqBPR0A)

* 題目為給定一Binary Tree的兩list資訊
* Inorder Traversal: 左中右
* Postorder Traversal: 左右中
* 求此Binary Tree結構
* 解法參考[105. Construct Binary Tree from Preorder and Inorder Traversal](/wJVgPFtFTD2MIOuEqBPR0A) 即可
* 特別注意:
* 因為postorder最尾為root
* 每次遞迴求當前root都會pop()最右邊
* 因此要先遞迴右子樹
* 才能遞迴求左子樹，才不會出錯

## Python:

from collections import defaultdict
class TreeNode():
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
    def insertLeft(self,node):
        if not self.left:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if not self.right:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)
        
class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        self.dic=defaultdict(int)
        for pos,node in enumerate(inorder):
            self.dic[node]=pos
        return self.build(0,len(inorder)-1,inorder,postorder)
    def build(self,start,end,inorder,postorder):
        if start>end:
            return None
        #最右邊為當前root
        root=TreeNode(postorder.pop())
        curPos=self.dic[root.val]
        #因為每次先pop處理最右邊，所以遞迴要先處理右子樹
        root.right=self.build(curPos+1,end,inorder,postorder)
        #再處理左子樹
        root.left=self.build(start,curPos-1,inorder,postorder)
        return root

                
result = Solution()
inorder = [4,2,5,1,6,3,7]
postorder = [4,5,2,6,7,3,1]
ans = result.buildTree(inorder,postorder)
ans.printTree()
print("postorder after :",postorder)
print("inorder after :",inorder)

'''
#法2 recursive 慢

class Solution:
    def buildTree(self, inorder, postorder):
        #recursive
        if not inorder or not postorder:
            return None
        root=TreeNode(postorder[-1])
        cur_pos = inorder.index(root.val)
        root.right=self.buildTree(inorder[cur_pos+1:],postorder[cur_pos:-1])
        root.left=self.buildTree(inorder[:cur_pos],postorder[:cur_pos])
        return root

'''