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

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