题解 | #Problem D# （二叉树的建树与遍历）

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

string s1, s2;

struct Tree{
    char data;
    Tree* left;
    Tree* right;
    Tree(char x): data(x), left(NULL), right(NULL) {} 
};

void PostOrder(Tree* &root)
{
    if(root == NULL) return;

    PostOrder(root->left);
    PostOrder(root->right);
    cout << root->data;
}

void build(Tree* & root, string s1, string s2)
{
    if(s1.size() == 0) return;

    if(root == NULL)
        root = new Tree(s1[0]);

    int j = s2.find(s1[0]);
    build(root->left, s1.substr(1, j), s2.substr(0, j));
    build(root->right, s1.substr(j + 1), s2.substr(j + 1));
}

int main() {
    while(cin >> s1 >> s2)
    {
        Tree* root = NULL;

        build(root, s1, s2);
        PostOrder(root);

        cout << endl;
    }
}