题解 | #二叉树遍历#

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

/*
    递归思想，先将当前左右序列进行分割，然后在进行当前左右序列的递归，输出当前最后一个元素
*/
void postOrder(string& preorder, string& midorder) {
    if (preorder.size() == 0) {
        return;
    }
    char root = preorder[0];
    int rootIndex = midorder.find(root);
    string leftPre = preorder.substr(1, rootIndex);
    string rightPre = preorder.substr(rootIndex + 1);
    string leftMid = midorder.substr(0, rootIndex);
    string rightMid = midorder.substr(rootIndex + 1);
    postOrder(leftPre, leftMid);
    postOrder(rightPre, rightMid);
    cout << root;
}

int main() {
    string preOrder, midOrder;
    while (cin >> preOrder >> midOrder) {
        postOrder(preOrder, midOrder);
        cout << endl;
    }
    return 0;
}