题解 | #二叉树遍历#

#include <iostream>
using namespace std;
struct treeNode {
    char data;
    treeNode* leftChild;
    treeNode* rightChild;
    treeNode(char c) {
        data = c;
        leftChild = NULL;
        rightChild = NULL;
    }
};
treeNode* build(string preStr, string inStr) {

    if (preStr.size() == 0) return NULL;
    char temp = preStr[0];
    int pos = inStr.find(temp); //pos等于左子树大小
    treeNode* root = new treeNode(temp);
    root->leftChild = build(preStr.substr(1, pos), inStr.substr(0, pos));
    root->rightChild = build(preStr.substr(1 + pos), inStr.substr(pos + 1));
    return root;
}
void postOrder(treeNode* root) {
    if (root == NULL) return;
    postOrder(root->leftChild);
    postOrder(root->rightChild);
    cout << root->data;
}
int main() {
    string pre, in;
    while (cin >> pre >> in) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        postOrder(build(pre, in));
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")