题解 | #二叉树遍历#

#include <iostream>
#include <queue>
using namespace std;


struct TreeNode{
    char data;
    TreeNode *leftchild;
    TreeNode *rightchild;
    TreeNode(char c):data(c),leftchild(NULL),rightchild(NULL){}

};

void visit(TreeNode *t){
    cout<<t->data;
    //printf("%c ",t->data);
}

void PostOrder(TreeNode *root){
    if(root==NULL)return;
    PostOrder(root->leftchild);
    PostOrder(root->rightchild);
    visit(root);
    return;
}

//由前序和中序反推后序遍历
TreeNode *build(string str1,string str2){
    if (str1.size()==0)return NULL;
    char c=str1[0];
    TreeNode *root=new TreeNode(c);
    int pos=str2.find(c);
    root->leftchild=build(str1.substr(1,pos),str2.substr(0,pos));
    root->rightchild=build(str1.substr(pos+1),str2.substr(pos+1));
    return root;
}

int main(){
    string str1,str2;
    while(cin>>str1>>str2){
        //cout<<"input"<<endl;
        TreeNode *t=build(str1,str2);
        //cout<<"ovre"<<endl;
        PostOrder(t);
        cout<<endl;
    }
    return 0;
}