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.

Solution:

The last element of postorder array is the root of the tree.

If we find this element in inorder array, we know the left part of inorder array is the left subtree and the right part of inorder array is the right subtree.

Therefore, we can build the tree recursively.



Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length != postorder.length) {
            return null;
        }
        return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
    
    public TreeNode helper(int[] inorder, int inLo, int inHi, int[] postorder, int postLo, int postHi) {
        if (inLo > inHi || postLo > postHi) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postHi]);
        int inRoot = inLo;
        for (int i = inLo; i <= inHi; i++) {
            if (inorder[i] == root.val) {
                inRoot = i;
                break;
            }
        }
        int rightLen = inHi - inRoot;
        root.left = helper(inorder, inLo, inRoot - 1, postorder, postLo, postHi - rightLen - 1);
        root.right = helper(inorder, inRoot + 1, inHi, postorder, postHi - rightLen, postHi - 1);
        return root;
    }
}