Construct Binary Tree from Preorder and Inorder Traversal @LeetCode

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

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

	package leetcode.tree;
	/**
	* Solution:
	* preorder: 7 10 4 3 1 (left) 2 8 11 (left)
	* inorder: 4 10 3 1 (left) 7 11 8 2 (right)
	*
	* 1. the first node in preorder must be root
	* 2. find out root position in inorder, and then root.left will be left part, same as root.right.
	* 3. Preorder: root, root.left, root.right --> (preStart+1, prestart+Index-inStart) will be left part, the rest are right part.
	* 4. do left subtree as 1-3, recursively.
	*
	* This is just a binary tree, not BST!
	*
	* Reference: http://leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html
	*
	* @author jeffwan
	* @date Feb 14, 2014
	*/
	public class InPreBuildTree {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
	if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0
	|| preorder.length != inorder.length) {
	return null;
	}
	int preorderLength = preorder.length;
	int inorderLength = inorder.length;
	return helper(preorder, inorder, 0, preorderLength - 1, 0, inorderLength - 1);
	}
	private TreeNode helper(int[] preorder,int[] inorder,int preStart,int preEnd,int inStart,int inEnd) {
	if (inStart > inEnd) {
	return null;
	}
	int rootIndex = 0;
	int rootValue = preorder[preStart];
	TreeNode root = new TreeNode(rootValue);
	for (int i = inStart; i <= inEnd; i++) {
	if (inorder[i] == rootValue) {
	rootIndex = i;
	break;
	}
	}
	int length = rootIndex - inStart;
	root.left = helper(preorder, inorder, preStart + 1, preStart + length, inStart, rootIndex - 1);
	root.right = helper(preorder, inorder, preStart + length + 1, preEnd, rootIndex + 1, inEnd);
	return root;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw InPreBuildTree.java hosted with ❤ by GitHub