输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
思路: 先来分析一下前序遍历和中序遍历得到的结果,
前序遍历第一位是根节点; 中序遍历中,根节点左边的是根节点的左子树,右边是根节点的右子树。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。
首先,根节点 是{ 1 }; 左子树是:前序{ 2,4,7 } ,中序{ 4,7,2 }; 右子树是:前序{ 3,5,6,8 } ,中序{ 5,3,8,6 };
这时,如果我们把左子树和右子树分别作为新的二叉树,则可以求出其根节点,左子树和右子树。
这样,一直用这个方式,就可以实现重建二叉树。
Java代码:
/**
* 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 prestart ,int preend,int [] pre,int instart,int inend, int [] in){
TreeNode tree = new TreeNode(pre[prestart]);
tree.left = null;
tree.right = null;
if ( prestart == preend && instart == inend){
return tree;
}
int root = 0;
for (root = instart ; root < inend ; root++){
if ( pre[prestart] == in[root]){
break;
}
}
int leftlength = root - instart;
int rightlength = inend - root;
if ( leftlength > 0){
tree.left = reConstructBinaryTree(prestart+1, prestart+leftlength , pre, instart, root-1, in);
}
if ( rightlength > 0){
tree.right = reConstructBinaryTree(prestart+1+leftlength, preend, pre, root+1, inend, in);
}
return tree;
}
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if ( pre == null || in == null){
return null;
}
TreeNode root = reConstructBinaryTree(0, pre.length-1, pre, 0, in.length-1, in);
return root;
}
}
c++代码如下:
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* Build(int* Pre,int* Vin ,int len){
if(!Pre || !Vin || len < 0){
return NULL;
}
int root_index = 0;
for(root_index = 0 ; root_index < len ; root_index++){
if(Vin[root_index] == Pre[0]){
break;
}
}
if(root_index == len){
return NULL;
}
TreeNode *root;
root = new TreeNode(Pre[0]);
root->left = root->right = NULL;
if(root_index > 0){
root->left = Build(Pre+1,Vin,root_index);
}
if(len-root_index-1 > 0){
root->right = Build(Pre+root_index+1,Vin+root_index+1,len-root_index-1);
}
return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
int len = pre.size();
int *Pre,*Vin;
Pre = new int[len];
Vin = new int[len];
for(int i = 0 ; i < len ; i++){
Pre[i] = pre[i];
Vin[i] = vin[i];
}
TreeNode *root = this->Build(Pre,Vin,len);
return root;
}
};