题解 | #二叉树遍历#

#include<iostream>
using namespace std;
struct btree{
    char data;
    btree* leftchild;
    btree* rightchild;
    btree(){}
    btree(char c):data(c),leftchild(nullptr),rightchild(nullptr){}
};
btree* build(string preorder,string inorder){
    //创建
    if(preorder.size()==0){
        return nullptr;
    }
    char c=preorder[0];
    btree* root=new btree(c);
    int position=inorder.find(c);
    root->leftchild=build(preorder.substr(1,position), inorder.substr(0,position));
    root->rightchild=build(preorder.substr(position+1), inorder.substr(position+1));
    return root;
}
void postorder(btree* root){
    //后序遍历
    if(root==nullptr){
        return;
    }
    postorder(root->leftchild);
    postorder(root->rightchild);
    cout<<root->data;
}
int main(){
    string str1,str2;
    while(cin>>str1>>str2){
        btree* root=build(str1, str2);
        postorder(root);
        cout<<endl;
    }
    return 0;
}