题解 | #二叉树遍历#

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

struct Node {
    char data;
    Node* leftT;
    Node* rightT;
    Node(char c): data(c), leftT(NULL), rightT(NULL){}
};

Node * build(string prestr, string midstr){
    if(prestr.length() == 0)
        return NULL;
    Node* node = new Node(prestr[0]);
    int pos = midstr.find(prestr[0]);//在中序字符串中找到根结点的坐标
    node->leftT = build(prestr.substr(1, pos), midstr.substr(0, pos));
    node->rightT = build(prestr.substr(pos + 1), midstr.substr(pos + 1));
    return node;
}
//后序遍历
void inOrder(Node* node){
    if(node == NULL)
        return;
    inOrder(node->leftT);
    inOrder(node->rightT);
    cout << node->data;
}

int main() {
    string str1, str2;
    while (cin >> str1 >> str2) {
        Node* root = build(str1, str2);
        inOrder(root);
        cout << endl;
    }

    return 0;
}