106. Construct Binary Tree from Inorder and Postorder Traversal

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

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

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution 1: DFS O(n); O(h)

    /**
     * Solution 1: DFS O(n); O(h)
     * Take the last element in Postorder array as the root.
     * Find the index of the root in the inorder array.
     * Then locate the range for left sub-tree and right sub-tree and do recursion.
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null) {
            return null;
        }

        return buildTree(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

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

        TreeNode root = new TreeNode(postorder[pe]);
        int rootIndex = is;
        for (; rootIndex <= ie; rootIndex++) {
            if (inorder[rootIndex] == root.val) {
                break;
            }
        }

        root.left = buildTree(inorder, postorder, is, rootIndex - 1, ps, ps + rootIndex - 1 - is);
        root.right = buildTree(inorder, postorder, rootIndex + 1, ie, pe - ie + rootIndex, pe - 1);
        return root;
    }