Construct Binary Tree from Inorder and Postorder Traversal @LeetCode

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

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

	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;
	}
	}
	}

view raw InPostBuildTree.java hosted with ❤ by GitHub