题解 | #二叉树遍历#

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

string s1, s2;

struct node {
    char val;
    struct node *left, *right;
    node() {}
    node(char _v) : val(_v) {}
};

node *build(int leftPre, int rightPre, int leftIn, int rightIn) {
    if (leftPre == rightPre) return nullptr;
    node *root = new node(s1[leftPre]);
    if ((rightPre - leftPre) == 1) return root;
    int cutIndex;
    for (cutIndex = leftIn; cutIndex < rightIn; cutIndex++) {
        if (s2[cutIndex] == s1[leftPre]) break;
    }
    root->left = build(leftPre + 1, leftPre + 1 + cutIndex - leftIn, leftIn, cutIndex);
    root->right = build(leftPre + 1 + cutIndex - leftIn, rightPre, cutIndex + 1, rightIn);
    return root;
}

void postOrder(node *root) {
    if (!root) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val;
}

int main() {
    while (cin >> s1 >> s2) {
        int len = s1.size();
        node *root = build(0, len, 0, len);
        postOrder(root);
        cout << endl;
    }
}

前序中序重建二叉树＋后序遍历，模板题