==========================================================================
原题链接
PAT甲级 1020 Tree Traversals
题目大意
给出N个结点的二叉树的后序序列和中序序列，输出该二叉树的层序遍历序列。
解题思路
根据后序序列和中序序列构造出二叉树的结构。如题例，后序序列的最后一个结点是4，是根结点。根据中序序列，4的左半部分是4的左子树，4的右半部分是4的右子树。将左右子树分别看作一个树，在对应后序序列找到最后一个结点（根结点），如此递归，即可实现二叉树的构造。 对二叉树进行层序遍历输出。使用queue队列结构，首先插入根结点，然后进入一个queue不为空的循环（输出队首结点的值，判断队首结点是否有左右子结点，若有则按顺序入队，弹出队首元素）。
示例代码
#include
#include
using namespace std;
struct Node{
int value;
Node* left;
Node* right;
};
int N, postord[30], midord[30];
Node* ConstructTree(int post_head, int post_tail, int mid_head, int mid_tail){
if(post_head>post_tail) return NULL;
//根据后序序列区间和中序序列区间构建二叉树，返回根节点的指针
Node* root = new Node;
root->value = postord[post_tail];
int index;//根节点在中序序列中的位置
for(index=mid_head; midord[index]!=postord[post_tail]; index++);
//左子树的节点个数
int left_len = index-mid_head;
//左子树
root->left = ConstructTree(post_head, post_head+left_len-1, mid_head, index-1);
//右子树
root->right = ConstructTree(post_head+left_len, post_tail-1, index+1, mid_tail);
感谢每一个认真阅读我文章的人，看着粉丝一路的上涨和关注，礼尚往来总是要有的：
① 2000多本Python电子书（主流和经典的书籍应该都有了）
② Python标准库资料（最全中文版）
③ 项目源码（四五十个有趣且经典的练手项目及源码）
④ Python基础入门、爬虫、web开发、大数据分析方面的视频（适合小白学习）
⑤ Python学习路线图（告别不入流的学习）
小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。
深知大多数初中级Python工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！
因此收集整理了一份《2024年Python爬虫全套学习资料》送给大家，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。
由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频
如果你觉得这些内容对你有帮助，可以添加下面V无偿领取！（备注：python）
来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频**
如果你觉得这些内容对你有帮助，可以添加下面V无偿领取！（备注：python） [外链图片转存中…(img-M1NfVsF2-1711059160140)]
参考链接
您阅读本篇文章共花了：
发表评论