Construct Binary Tree from Inorder and Postorder Traversal @leetcode

InPostBuildTree.java

package leetcode.tree;

/**
 * Solution:
 * postorder: 4 1 3 10 (left)    11 8 2 (right)    7
 * inorder:   4 10 3 1 (left)    7      11 8 2 (right) 
 * 
 * Same as Preorder - Inorder Construction. Only difference is sequence and index handling.
 * 
 * @author jeffwan
 * @date Feb 14, 2014
 */
public class InPostBuildTree {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		if (inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0 ||
				inorder.length != postorder.length) {
			return null;
		}

		int inorderLength = inorder.length;
		int postorderLength = postorder.length;

		return helper(inorder, postorder, 0, inorderLength - 1, 0, postorderLength - 1);
	}


	private TreeNode helper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) {
		if (inStart > inEnd) {
			return null;
		}

		int rootIndex = 0;
		int rootValue = postorder[postEnd];
		TreeNode root = new TreeNode(rootValue);

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

		int length = rootIndex - inStart;

		// Divide & Conquer
		root.left = helper(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + length - 1);
		root.right = helper(inorder, postorder, rootIndex + 1, inEnd, postStart + length, postEnd - 1);
		
		return root;
	}
	
	// TreeNode 
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode (int x) {
			val = x;
		}
	}
}