题解 | #二叉树遍历#

二叉树遍历

https://www.nowcoder.com/practice/6e732a9632bc4d12b442469aed7fe9ce

#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");
    }
}

全部评论

相关推荐

程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
06-10 21:15
门头沟学院 Java
宁阿:好多这种没🧠的公司,他们估计都不知道毕业的人不能给安排实习岗
实习吐槽大会
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务