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

/**
 * 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 buildTree(inorder, 0, inorder.length-1, postorder, 0, inorder.length-1);
    }

    public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart <= inEnd) {

            int rootValue = postorder[postEnd];

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

            if (position > inEnd) return null;

            TreeNode left = buildTree(inorder, inStart, position - 1, postorder, postStart, position - 1 - inStart + postStart);
            TreeNode right = buildTree(inorder, position + 1, inEnd, postorder, position - inStart + postStart, postEnd - 1);

            TreeNode root = new TreeNode(rootValue);
            root.left = left;
            root.right = right;

            return root;
        } else {
            return null;
        }

    }
}