剑指Offer：重建二叉树【7】
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
题目分析
首先我们要了解前序和中序遍历的特点：
从图中不难发现，对于前序遍历的第一个节点1，在中序遍历中处于中间位置，且两侧分别对应他的左右子树。这是因为中序遍历打印的顺序为：左孩子——当前元素——右孩子，而前序遍历是首先打印当前元素。
重建二叉树的重构函数分为三个步骤：
- 首先要找到当前元素节点，即pre中的第一个，
- 接着在中序遍历中找到它的左右子树（此处表现为对前序数组、中序数组的分割操作），以便构造他的左右孩子。
- 最后再将左右子树在分别放到重构函数中。
比如此时，我们找到1的右子树（356），如下图，它实质上适合上图一样的，只不过此时是以3位根节点，其他操作是一样。
此时重复操作：找到当前元素节点，即pre中的第一个，接着便可以在中序遍历中找到他的左右子树，以便构造他的左右孩子。发现他没有右孩子，只有左孩子，那就将左孩子放入重构函数中，即
此时重复操作：找到当前元素节点，即pre中的第一个，接着便可以在中序遍历中找到他的左右子树，以便构造他的左右孩子。发现他没有右孩子，只有左孩子，那就将左孩子放入重构函数中，即
直到分割成叶子节点，不存在左右子树，他无法再进行分割，故返回自己。叶子节点返回后，其父节点的左右子树分别有了指向，便返回，一步一步向上返回，最后会返回整个二叉树。
Java实现代码
public class BuildTree {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode root=ConstructCore(pre,0,pre.length-1,in,0,in.length-1);
return root;
}
public TreeNode ConstructCore(int[] pre,int startPre,int endPre,int[] in,int startIn,int endIn)
{
if(startPre>endPre||startIn>endIn)
return null;
TreeNode node = new TreeNode(pre[startPre]);
for(int i=startIn;i<=endIn;i++)
{
if(in[i]==pre[startPre])
{
node.left = ConstructCore(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
node.right =ConstructCore(pre,startPre+i-startIn+1,endPre,in,i+1,endIn);
break;
}
}
return node;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}