题解 | 二叉树遍历

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

typedef struct Node {
    char root;
    Node* rchild, *lchild;
} Node;

Node* recover(string preOrderString, string midOrderString) {
    char c = preOrderString.at(0);
    // 建立新节点
    Node* cur = new Node;
    cur->root = c;
    cur->lchild = NULL;
    cur->rchild = NULL;
    int pos = midOrderString.find(c);
    // 结束条件
    if (preOrderString.size() == 0) {
        return cur;
    }
    if (pos != 0) {
        string preTemp = preOrderString.substr(1, pos);
        string midTemp = midOrderString.substr(0, pos);
        cur->lchild = recover(preTemp, midTemp);
    }
    if (pos + 1 != preOrderString.size()) {
        string preTemp = preOrderString.substr(pos+1);
        string midTemp = midOrderString.substr(pos+1);
        cur->rchild = recover(preTemp, midTemp);
    }
    return cur;
}

void postOrder(Node* node){
    if(node->lchild != NULL)
        postOrder(node->lchild);
    if(node->rchild != NULL)
        postOrder(node->rchild);
    cout << node->root;
}

int main() {
    string preOrderString;
    string midOrderString;
    while (cin >> preOrderString >> midOrderString) {
        // 重建二叉树
        Node* node = new Node;
        node = recover(preOrderString, midOrderString);
        // 后序遍历
        postOrder(node);
        cout << endl;
    }
}