题解 | #二叉树遍历#

#include <iostream>

using namespace std;

struct treenode{
    char data;
    treenode* left;
    treenode* right;
    treenode(char c): data(c), left(nullptr), right(nullptr){};
};

treenode* buildtree(string s1, string s2){
    if(!s1.size())return nullptr;
    if(!s2.size())return nullptr;
    if(s1.size()==1)return new treenode(s1[0]);
    if(s2.size()==1)return new treenode(s2[0]);
    treenode* root = new treenode(s1[0]);
    int pos = s2.find(s1[0]);
    root->left = buildtree(s1.substr(1,pos), s2.substr(0,pos));
    root->right=buildtree(s1.substr(pos+1), s2.substr(pos+1));
    return root;
}

void dfs(treenode* root){
    if(!root)return;
    dfs(root->left);
    dfs(root->right);
    cout<<root->data;
}

int main() {
    string s1,s2;
    while (cin >> s1 >> s2) { // 注意 while 处理多个 case
        treenode *ans;
        ans = buildtree(s1,s2);
        dfs(ans);
        puts("");
    }
    return 0;
}
// 64 位输出请用 printf("%lld")