本文共 1783 字，大约阅读时间需要 5 分钟。

此分类专栏只写关于剑指 offer的66道题！！！

题目：重建二叉树

题目描述： 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 解题思想分析： 递归思想，每次将左右两颗子树当成新的子树进行处理，中序的左右子树索引很好找，前序的开始结束索引通过计算中序中左右子树的大小来计算，然后递归求解，直到startPre>endPre||startIn>endIn说明子树整理完到。方法每次返回左子树和右子树的根节点。 即分析： 在二叉树的前序遍历序列中，第一个数字总是树的根节点的值。但在中序遍历序列中根节点的值在序列的中间，左子树的节点的值位于根节点的值的左边，而右子树的节点的值位于根节点的值的右边，因此我们需要扫描中序遍历序列，才能找到根节点的值。 从上面可知，题目中前序遍历的第一个节点{1}一定是这棵二叉树的根节点，根据中序遍历序列，可以发现中序遍历序列中节点{1}之前的{4,7,2}是这棵二叉树的左子树，{5,3,8,6}是这棵二叉树的右子树。然后，对于左子树，递归地把前序子序列{2,4,7}和中序子序列{4,7,2}看成新的前序遍历和中序遍历序列。此时，对于这两个序列，该子树的根节点是{2}，该子树的左子树为{4,7}、右子树为空，如此递归下去（即把当前子树当做树，又根据上述步骤分析）。{5,3,8,6}这棵右子树的分析也是这样。

/** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {        int startPre = 0;		int endPre = pre.length - 1;		int startIn = 0;		int endIn = in.length - 1;		return rebuildTree(pre, startPre, endPre, in, startIn, endIn);	}	private TreeNode rebuildTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {	/*	     startPre>endPre||startIn>endIn说明子树整理完到	*/		if (startPre > endPre || startIn > endIn) {			return null;		}		//找到根节点：前序第一个为根节点		TreeNode root = new TreeNode(pre[startPre]);		int index = startIn;		for (; index <= endIn; index++) {			//当中序中的遍历到与父节点相同的节点时，退出			//此时index的左面是左节点			//index的右面是右节点			if (in[index] == pre[startPre]) {				break;			}		}		//递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点		root.left = rebuildTree(pre, startPre + 1, startPre + (index - startIn), in, startIn, index - 1);		root.right = rebuildTree(pre, startPre + (index - startIn) + 1, endPre, in, index + 1, endIn);		return root;	}}