Problem

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

思路

• 中序： 左子树，根，右子树
• 后序： 左子树，右子树，根
• 从后序找到根的位置，在中序中找到根， 组成根，然后以同样的方式组成其左节点和右节点

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, 0, inorder.length - 1, postorder, postorder.length - 1);
    }

    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postIndex) {
        if (inStart > inEnd || postIndex < 0) return null;

        TreeNode root = new TreeNode (postorder[postIndex]);

        int inIndex = inStart;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
            }
        }

        root.left = buildTree(inorder, inStart, inIndex - 1, postorder, postIndex - 1 - (inEnd - inIndex));
        root.right = buildTree(inorder, inIndex + 1, inEnd, postorder, postIndex - 1);

        return root;
    }