题解 | 重建二叉树

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

//定义树结点
typedef struct Node {
    char data;
    struct Node* rchild, * lchild;
} BiTNode, *BiTree;

BiTNode* CreatTree(string prestr, string instr) {
    if (prestr.size() == 0 || instr.size() == 0)return NULL;
    char c = prestr[0];//先序序列第一个元素为根
    BiTNode* root = new BiTNode();
    root->data = c;
    //中序序列中，以先序第一个元素分左右子树的中序序列
    int pos = instr.find(c);
    //传入左子树的先序序列，左子树的中序序列
    root->lchild = CreatTree(prestr.substr(1, pos), instr.substr(0, pos));
    //传入右子树的先序序列，右子树的中序序列
    root->rchild = CreatTree(prestr.substr(pos + 1), instr.substr(pos + 1));

    return root;
}

//后序遍历
void PostOrder(BiTree T) {
    if (T == NULL)return;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    printf("%c", T->data);
}

int main() {
    string prestr, instr;
    while (getline(cin, prestr)) {
        getline(cin, instr);
        BiTNode* root = CreatTree(prestr, instr);
        PostOrder(root);
        printf("\n");
    }
    return 0;

}