Question:

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

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

Thinking:

Inorder traversal will search in order: left, root, right;

Postorder travelsal will search in order: left, right, root.

So we can find the root in postorder and search it in inorder by the value. And find root’s left child and right child node by recursion.

public TreeNode buildTree(int[] inorder, int[] postorder) {
    int l = inorder.length;
    if (l == 0)
        return null;
    TreeNode root = new TreeNode(postorder[l-1]);
    TreeNode left = null;
    TreeNode right = null;
    int index = 0;
    for (; index < l; index++){
        if (inorder[index] == postorder[l-1])
            break;
    }


    if (index > 0){
        int[] leftinorder = new int[index];
        int[] leftpostorder = new int[index];
        System.arraycopy(inorder, 0, leftinorder, 0, index);
        System.arraycopy(postorder, 0, leftpostorder, 0, index);
        left = buildTree(leftinorder, leftpostorder);
    }
    if (index < l-1){
        int[] rightinorder = new int[l-index-1];
        int[] rightpostorder = new int[l-index-1];
        System.arraycopy(inorder, index+1, rightinorder, 0, l-index-1);
        System.arraycopy(postorder, index, rightpostorder, 0, l-index-1);
        right = buildTree(rightinorder, rightpostorder);
    }
    root.left = left;
    root.right = right;

    return root;
}

By the way, this code can be improved because in Java we can not easily get the subarray and I use the System.arraycopy. It can be replaced by recording the postion of array.