题解 | #二叉树遍历#

#include<iostream>
#include<string>

using namespace std;

struct TreeNode {
    char data;
    TreeNode *lchild=NULL,*rchild=NULL;
};

void BuildTree(TreeNode *root,string pre,string mid){
    root->data = pre[0];
    if(mid.size()==1) return;
    
    int pos = mid.find(pre[0]);
    string mid_left = mid.substr(0,pos);
    string mid_right = mid.substr(pos+1);
    string pre_left = pre.substr(1,mid_left.size());
    string pre_right = pre.substr(mid_left.size()+1);
    
    
    if(mid_left.size()>0){
        root->lchild = new TreeNode();
        BuildTree(root->lchild,pre_left,mid_left);
    }
    if(mid_right.size()>0){
        root->rchild = new TreeNode();
        BuildTree(root->rchild,pre_right,mid_right);
    }
}
void PostOrder(TreeNode* root){
    if(root==NULL) return;
    
    if(root->lchild!=NULL) PostOrder(root->lchild);
    if(root->rchild!=NULL) PostOrder(root->rchild);
    
    cout<<root->data;
}

int main(){
    string pre,mid;
    while(cin>>pre>>mid){
        TreeNode* root = new TreeNode();
        BuildTree(root,pre,mid);
        PostOrder(root);
        cout<<endl;
    }
    
    
    return 0;
}