# 0105. Construct Binary Tree from Preorder and Inorder Traversal
###### tags: `Leetcode` `Medium` `Recursion` `Tree` `Preorder Traversal` `Inorder Traversal`
Link: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
## 思路
[思路参考](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/1102530/construct-binary-tree-from-preorder-and-inorder-traversal/?orderBy=most_votes)
如果锁定了一个root val就可以通过inorder array找到left subtree和right subtree都有哪些值
那么如何找到root val 对于一个postorder array来说 它的第一个值就是当前tree的root
这时我们找到了root 并且找到了left 和 right subtree都有哪些值
那么我们如何找到left 和right subtree的root呢？
由于是preorder我们从前往后遍历的时候会遇到left subtree的root 把left subtree的所有element走完才是right subtree的root 因此我们需要先把left subtree建完 才能建right subtree (这样才能保证我们可以按照postorder从前往后的顺序给定当前root的值) 所以我们用recursion先建left subtree再建right subtree
## Code

class Solution {
    int preOrderIdx = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for(int i=0; i<inorder.length; i++){
            inorderMap.put(inorder[i], i);
        }
        return arrayToTree(inorderMap, preorder, 0, inorder.length-1);
    }
    public TreeNode arrayToTree(Map<Integer, Integer> inorderMap, int[] preorder, int left, int right){
        if(left>right) return null;
        TreeNode root = new TreeNode(preorder[preOrderIdx++]);
        root.left = arrayToTree(inorderMap, preorder, left, inorderMap.get(root.val)-1);
        root.right = arrayToTree(inorderMap, preorder, inorderMap.get(root.val)+1, right);
        return root;
    }
}

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        preorderIdx = 0
        inorderDict = {}
        for i, val in enumerate(inorder):
            inorderDict[val] = i
        
        def arrayToTree(left: int, right: int) -> Optional[TreeNode]:
            nonlocal preorderIdx
            if left>right: return None
            root = TreeNode(preorder[preorderIdx])
            preorderIdx += 1
            root.left = arrayToTree(left, inorderDict[root.val]-1)
            root.right = arrayToTree(inorderDict[root.val]+1, right)
            return root

        return arrayToTree(0, len(inorder)-1)