面试题6：重建二叉树.md

#面试题6:重建二叉树

题目：

输入二叉树的前序遍历和中序遍历的结果,重建出该二叉树。假设前序遍历和中序遍历结果中都不包含重复的数字,例如输入的前序遍历序列 {1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}重建出如图所示的二叉 树。

解题思路：

前序遍历第一个结点是父结点，中序遍历如果遍历到父结点，那么父结点前面的结点是左子树的结点，后边的结点的右子树的结点，这样我们可以找到左、右子树的前序遍历和中序遍历，我们可以用同样的方法去构建左右子树，可以用递归完成。

代码：

public class BinaryTreeNode {

	public static int value;
	public BinaryTreeNode leftNode;
	public BinaryTreeNode rightNode;
}

public class Solution {

	public static BinaryTreeNode constructCore(int[] preorder, int[] inorder) throws Exception {
		if (preorder == null || inorder == null) {
			return null;
		}
		if (preorder.length != inorder.length) {
			throw new Exception("长度不一样，非法的输入");
		}
		BinaryTreeNode root = new BinaryTreeNode();
		for (int i = 0; i < inorder.length; i++) {
			if (inorder[i] == preorder[0]) {
				root.value = inorder[i];
				System.out.println(root.value);
				root.leftNode = constructCore(Arrays.copyOfRange(preorder, 1, i + 1),
						Arrays.copyOfRange(inorder, 0, i));
				root.rightNode = constructCore(Arrays.copyOfRange(preorder, i + 1, preorder.length),
						Arrays.copyOfRange(inorder, i + 1, inorder.length));
			}
		}
		return root;

	}
}