###### tags: `Leetcode` `medium` `tree` `python` `Top 100 Liked Questions`

# 105. Construct Binary Tree from Preorder and Inorder Traversal

## [題目連結:]https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

## 題目:
Given two integer arrays ```preorder``` and ```inorder``` where ```preorder``` is the preorder traversal of a binary tree and ```inorder``` is the inorder traversal of the same tree, construct and return the binary tree.


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

## 解題想法:
兄弟題目[106. Construct Binary Tree from Inorder and Postorder Traversal](/5CFsONSgTu61B_VFBxlLjw)
* 題目為給定一Binary Tree的兩list資訊
* Preorder Traversal: 中左右
* Inorder Traversal: 左中右
* 求此Binary Tree結構
* 解法:
* 單純Recursive(慢)
* 優化: 使用dic存inorder每個node的位置，方便search
* 每次使用root後皆從preorder刪除
* 遞迴依照inorder視角，讓inorder切割即可

## Python: (Sol1)
* 因為preorder: 最左邊一定為root，
* 判斷此root在inorder list中的位置: curPos
* 左右子樹進行遞迴
* root.left範圍: inorder[:curPos]
* 對於自己處於的preorder也取curPos數量: preorder[1:curPos+1]
* root.right範圍: inorder[curPos+1:]
* 對於自己處於的preorder也取curPos數量: preorder[curPos+1:]

ex: 
preorder = ['1',2,4,5,3,6,7]
inorder = [4,2,5,'1',6,3,7]

root=TreeNode(1)
curPos=3
#自己取curPos個數量的node
root.left=build(pre[1:3+1], in[:3]) 
    * pre=[2,4,5] in=[4,2,5]
root.right=build(pre[3+1:], in[3+1:])
    * pre=[3,6,7] in=[6,3,7]

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, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder or not inorder:
            return None
        root = TreeNode(preorder[0])
        #找對應於inorder的位置
        for pos,node in enumerate(inorder):
            if node==root.val:
                curPos=pos
                break
        #上述可用curPos=inorder.index(root.val)代替
        root.left=self.buildTree(preorder[1:curPos+1],inorder[:curPos])
        root.right=self.buildTree(preorder[curPos+1:],inorder[curPos+1:])
        return root
                
result = Solution()
preorder = [1,2,4,5,3,6,7]
inorder = [4,2,5,1,6,3,7]
ans = result.buildTree(preorder,inorder)
ans.printTree() #[1, 2, 3, 4, 5, 6, 7]

## Python: (Sol2) 優化
* 代碼已標注解釋
* 特別注意:
* 因為preorder最左邊為root
* 每次遞迴求當前root都會pop(-1)最左邊
* 因此要先遞迴求左子樹
* 才能遞迴求右子樹，才不會出錯

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, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: 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,preorder,inorder)
    def build(self,start,end,preorder,inorder):
        if start>end:
            return None
        #用pop直接刪掉當前的root，讓pre越來越短
        root=TreeNode(preorder.pop(0))
        #得到在inorder對應的位置
        curPos=self.dic[root.val]
        #遞迴: 皆依照inorder視角即可
        #因為每次先pop處理最左邊，所以遞迴要先處理左子樹
        root.left=self.build(start,curPos-1,preorder,inorder[:curPos])
        #再處理右子樹
        root.right=self.build(curPos+1,end,preorder,inorder[curPos+1:])
        return root

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