Reconstruct binary tree

题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

package interview;

/**
 * Definition for binary tree
 * 
 */

public class Solution2 {

	public static void main(String[] args) {
		int[] pre = new int[] { 1, 2, 4, 7, 3, 5, 6, 8 };

		int[] in = new int[] { 4, 7, 2, 1, 5, 3, 8, 6 };
		
		long startTime = System.currentTimeMillis();
		for(int i =0; i< 100000; ++ i) {
		new Solution2().reConstructBinaryTree2(pre, in);
		}
		long endTime = System.currentTimeMillis();
		System.out.println("" + (endTime - startTime));
		
		
		startTime = System.currentTimeMillis();
		for(int i =0; i< 100000; ++ i) {
		new Solution2().reConstructBinaryTree2(pre, in);
		}
		 endTime = System.currentTimeMillis();
		
		System.out.println("" + (endTime - startTime));
	}

	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public TreeNode reConstructBinaryTree2(int[] pre, int[] in) {
		TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
		return root;
	}

	// 前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
	private TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {

		if (startPre > endPre || startIn > endIn)
			return null;
		TreeNode root = new TreeNode(pre[startPre]);

		for (int i = startIn; i <= endIn; i++)
			if (in[i] == pre[startPre]) {
				root.left = reConstructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
				root.right = reConstructBinaryTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
			}

		return root;
	}

	public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
		
		int[] aPreStart = new int[in.length];
		int[] aPreEnd = new int[in.length];
		int[] aInStart = new int[in.length];
		int[] aInEnd = new int[in.length];
		TreeNode[] aRootNodes = new TreeNode[in.length];
		
		int count = 0;
		// push the parameters
		aPreStart[count] = 0;
		aPreEnd[count] = pre.length - 1;
		aInStart[count] = 0;
		aInEnd[count] = in.length - 1;
		TreeNode theRootNode = new TreeNode(pre[aPreStart[count]]);
		aRootNodes[count] = theRootNode;
		
		count++;
		while (count > 0) {
			int preStart = aPreStart[count - 1];
			int preEnd = aPreEnd[count - 1];
			int inStart = aInStart[count - 1];
			int inEnd = aInEnd[count - 1];
			TreeNode rootNode = aRootNodes[count - 1];
			int root = pre[preStart];
			//System.out.println("count is " + count);
			count--;
			if (preStart == preEnd) {
				// leaf
				continue;
			} else {
				int middle = -1;
				for (int i = inStart; i <= inEnd; ++i) {
					if (in[i] == root) {
						middle = i;
						break;
					}
				}
				//System.out.println("middle is " + middle);
				
				if (middle - 1 >= inStart) {
					
					aInStart[count] = inStart;
					aInEnd[count] = middle - 1;
					
					aPreStart[count] = preStart + 1;
					aPreEnd[count] = preStart + 1 + (middle - 1 - inStart + 1) - 1;
					
					TreeNode leftNode = new TreeNode(pre[aPreStart[count]]);
					rootNode.left = leftNode;
					aRootNodes[count] = leftNode;
					
					count++;
				}
				
				if (inEnd >= middle + 1) {

					aInStart[count] = middle + 1;
					
					aInEnd[count] = inEnd;

					aPreStart[count] = preEnd - (inEnd - middle - 1 + 1) + 1;
					
					aPreEnd[count] = preEnd;

					TreeNode rightNode = new TreeNode(pre[aPreStart[count]]);
					rootNode.right = rightNode;

					aRootNodes[count] = rightNode;

					count++;
				}
			}
		}
		return theRootNode;

	}
}