题解 | #二叉树遍历#

#include<cstdio>
#include<string>

using namespace std;

struct TreeNode {
    char data;
    TreeNode* LChild;
    TreeNode* RChild;
};
TreeNode* rebuild(string PreOrder, string MidOrder ) {
    //rebuild返回子树根节点地址
    if (PreOrder.size() == 0) {
        return NULL;
    } else {
        //从先序中确定根
        char rootnode = PreOrder[0];
        TreeNode* pa = new TreeNode;//在堆上申请新的二叉树结点
        pa->data = rootnode;
        //拿rootnode切割中序(根）
        int pos = MidOrder.find(rootnode);//rootnode在中序中的下标
        //PreOrder.substr(1,pos);//substr 切割从a开始长度为b的字串
        //PreOrder.substr(pos+1);//到最后
        pa->LChild = rebuild(PreOrder.substr(1, pos), MidOrder.substr(0, pos));
        //递归处理左边左孩子
        pa->RChild = rebuild(PreOrder.substr(pos + 1), MidOrder.substr(pos + 1));
        //递归处理右孩子
        return pa;//返回根的值
    }
}
void LasOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    LasOrder(root->LChild);
    LasOrder(root->RChild);
    printf("%c", root->data);
}
int main() {
    char MidOrder[30];
    char PreOrder[30];
    while (scanf("%s%s", PreOrder, MidOrder) != EOF) {
        TreeNode* root ;
        root = rebuild(PreOrder, MidOrder);
        LasOrder(root);
        printf("\n");
    }
}