# 106 Construct Binary Tree from Inorder and Postorder Traversal

Concept:

postorder的最後一個就是root。

知道root是誰之後，就可以去inorder找到root的位置，

inorder中root左邊的element們就是左子樹，右邊的element就是右子樹。

root.left連到左子樹的root，root.right連到右子樹的root。

可用recursive達成

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return create(inorder, postorder, 0, inorder.length -1, 0, postorder.length -1);
    }

    TreeNode create(int[] inorder, int[] postorder, int is, int ie, int ps, int pe){
        if(ps>pe)
            return null;

        TreeNode node = new TreeNode(postorder[pe]);
        int pos = 0;
        for(int i = is; i<=ie; i++){
            if(inorder[i] == node.val){
                pos = i;
                break;
            }
        }
        node.left = create(inorder, postorder, is, pos-1, ps, ps+pos-is-1);
        node.right = create(inorder, postorder, pos + 1, ie, pe - ie + pos, pe - 1);
        return node;
    }
}