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.

Analysis:

If we look at postorder array in the order of last element to first element. We know that postorder[len-1] element is root, we search this element in inorderarray, then we divide inorderarray into 2 part, left and right. We go right first and firgure out its root by looking at postorder[len-2], recursively, we can build the tree.

Complexity:

Time: O(N)

Space: O(logn)

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

    int postindex = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null || postorder.length == 0)
        {
            return null;
        }
        postindex = postorder.length-1;
        return build(inorder, postorder, 0, postorder.length-1);
    }

    private TreeNode build(int[] inorder, int[] postorder, int s, int e)
    {
        if(s > e)
        {
            return null;
        }
        if(s == e)
        {
            postindex--;
            return new TreeNode(inorder[s]);
        }

        int index = s;
        for(int i=s; i<=e; i++)
        {
            if(inorder[i] == postorder[postindex])
            {
                postindex--;
                index = i;
                break;
            }
        }
        TreeNode root = new TreeNode(inorder[index]);
        root.right = build(inorder, postorder, index+1, e);
        root.left = build(inorder, postorder, s, index-1);
        return root;
    }

}