题目描述
利用前序和中序重建树
C++ 代码
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
unordered_map<char,int> pos;
string a,b;
struct TreeNode{
char val;
TreeNode* left,*right;
TreeNode(char x): val(x),left(NULL),right(NULL){};
};
TreeNode* build(int m,int n,int x,int y){
if(m>n) return NULL; //终止的条件
auto root = new TreeNode(a[m]);
int k = pos[a[m]];
root->left = build(m+1,m+k-x,x,k-1);
root->right = build(m+k-x+1,n,k+1,y);
return root;
}
void lastorder(TreeNode* root){
if(!root) return;
lastorder(root->left);
lastorder(root->right);
cout << root->val ;
}
int main(){
while(cin >> a && cin >> b){
int n=a.size();
for(int i=0;i<n;i++) pos[b[i]]=i;
auto root = build(0,n-1,0,n-1);
lastorder(root);
cout << endl;
}
return 0;
}