Construct Binary Tree from Inorder and Postorder Traversal

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

Example:

in-order:   4 2 5  (1)  6 7 3 8
post-order: 4 5 2  6 7 8 3  (1)

从后序遍历的顺序(左右中)我们可以观察到root永远会在最后一个位置(1), 然后我们就可以通过查找中序遍历的结果将中序遍历分为左子树与右子树(注意index的位置，找到多少数字在左子树，多少数字在右子树)，之后就可以递归构造root的左子树与右子树

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

    public TreeNode buildTree(int inStart, int inEnd, int[] inorder, int postStart, int postEnd, int[] postorder) {
        if(inStart > inEnd || postStart > postEnd) {
            return null;
        }            

        int rootValue = postorder[postEnd];
        int rootIndexInorder = 0;

        for (int i=inStart; i<=inEnd; i++) {
            if (rootValue == inorder[i]) {
                rootIndexInorder = i;
                break;
            }
        }

        //left sub tree length
        int length = rootIndexInorder-inStart;
        TreeNode root = new TreeNode(rootValue);

        //(rootIndex-inStart-1) is to get the length of left subtree.
        root.left = buildTree(inStart, rootIndexInorder-1, inorder, postStart, postStart+length-1, postorder);
        //left subtree end index + 1 is right subtree start index
        root.right = buildTree(rootIndexInorder+1, inEnd, inorder, postStart+length-1+1, postEnd-1, postorder);        
        return root;        
    }

Follow up question: Why can't we construct a binary tree from preorder and postorder traversal?

Answer: there will be multiple results: [1,2] [2,1]

  1         1            
 /           \
2             2