题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
图1 根据前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}重建的二叉树
二叉树结点的定义如下：
代码语言：javascript复制 struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode＊ m_pLeft;
BinaryTreeNode＊ m_pRight;
};在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，才能找到根结点的值。
如图2所示，前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列，就能确定根结点的值的位置。根据中序遍历特点，在根结点的值1前面的3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。
由于在中序遍历序列中，有 3 个数字是左子树结点的值，因此左子树总共有3 个左子结点。同样，在前序遍历的序列中，根结点后面的3 个数字就是 3 个左子树结点的值，再后面的所有数字都是右子树结点的值。这样我们就在前序遍历和中序遍历两个序列中，分别找到了左右子树对应的子序列。
图2 在二叉树的前序遍历和中序遍历的序列中确定根结点的值、左子树结点的值和右子树结点的值
既然我们已经分别找到了左、右子树的前序遍历序列和中序遍历序列，我们可以用同样的方法分别去构建左右子树。也就是说，接下来的事情可以用递归的方法去完成。在想清楚如何在前序遍历和中序遍历的序列中确定左、右子树的子序列之后，我们可以写出如下的递归代码
1、C
代码语言：javascript复制class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin)
{
if(pre.size() != vin.size())
return NULL;
int rootIndex=0;
int size = pre.size();
if(size==0){
return NULL;
}
//查找根节点在先序遍历数组中的下标
TreeNode *treeNode=new TreeNode(pre[0]);
for(int i=0;i<size;i ) {
//中序遍历数组中的第一个位置是根节点
if(vin[i]==pre[0]) {
rootIndex=i;
break;
}
}
//将先序的遍历结果分成两份，一份是左子树，一份是右子树
int leftlength = rootIndex;
int rightlength = size - 1 - rootIndex;
vector<int> preLeft(leftlength),vinLeft(leftlength);;
vector<int> preRight(rightlength),vinRight(rightlength);
// 把左右子树填写好
for(int i = 0; i < size; i )
{
if(i < leftlength)
{
preLeft[i] = pre[i 1];
vinLeft[i] = vin[i];
}
else if(i > leftlength)
{
preRight[i-leftlength-1] = pre[i];
vinRight[i-leftlength-1] = vin[i];
}
}
treeNode->left=reConstructBinaryTree(preLeft,vinLeft);
treeNode->right= reConstructBinaryTree(preRight,vinRight);
return treeNode;
}
void preVisit(TreeNode* treeNode){
if(treeNode==NULL){
return;
}
cout << treeNode->val << ",";
preVisit(treeNode->left);
preVisit(treeNode->right);
}
void midVisit(TreeNode* treeNode){
if(treeNode==NULL){
return;
}
midVisit(treeNode->left);
cout << treeNode->val << ",";
midVisit(treeNode->right);
}
};2、Java
代码语言：javascript复制package offer.reConstructBinaryTree;
public class Solution {
//pre:先序 in:中序
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode treeNode=new TreeNode(pre[0]);
//查找根节点在先序遍历数组中的下标
int rootIndex=0;
for(int i=0;i<in.length;i ) {
//中序遍历数组中的第一个位置是根节点
if(in[i]==pre[0]) {
rootIndex=i;
}
}
//将先序的遍历结果分成两份，一份是左子树，一份是右子树
int[] preLeft=new int[rootIndex];
int[] preRight=new int[pre.length-rootIndex-1];
for(int i=0;i<rootIndex;i ) {
preLeft[i]=pre[i 1];
}
for(int i=0;i<pre.length-rootIndex-1;i ) {
preRight[i]=pre[rootIndex 1 i];
}
//将中序的遍历的结果分为两份，一份是左子树，一份是右子树
int[] midLeft=new int[rootIndex];
int[] midRight=new int[in.length-rootIndex-1];
for(int i=0;i<rootIndex;i ) {
midLeft[i]=in[i];
}
for(int i=0;i<in.length-rootIndex-1;i ) {
midRight[i]=in[rootIndex i 1];
}
if(in.length>0&pre.length>0) {
if(preLeft.length>0) {
treeNode.left=reConstructBinaryTree(preLeft,midLeft);
}
if(preRight.length>0) {
treeNode.right= reConstructBinaryTree(preRight,midRight);
}
}
return treeNode;
}
public void preVisit(TreeNode treeNode){
if(treeNode==null){
return;
}
System.out.print(treeNode.val ",");
preVisit(treeNode.left);
preVisit(treeNode.right);
}
public void midVisit(TreeNode treeNode){
if(treeNode==null){
return;
}
midVisit(treeNode.left);
System.out.print(treeNode.val ",");
midVisit(treeNode.right);
}
public static void main(String[] args) {
//测试
int[] pre= {1,2,4,7,3,5,6,8};
int[] in= {4,7,2,1,5,3,8,6};
Solution solution=new Solution();
TreeNode treeNode=solution.reConstructBinaryTree(pre,in);
solution.preVisit(treeNode);
System.out.println();
solution.midVisit(treeNode);
System.out.println();
}
}
