【GPLT】L2-006 树的遍历
【GPLT】L2-006 树的遍历
喜欢ctrl的cxk
发布于 2019-11-08 13:38:53
发布于 2019-11-08 13:38:53
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/88776609
题目描述：
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入描述：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出描述：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7输出样例：
4 1 6 3 5 7 2解题思路：
建立三个vector，中序遍历in、后序遍历post、层序遍历level（level初始化为-1，-1表示此处没有结点）。自定义函数levelorder()的作用是根据中序和后序得到层序遍历，四个参数：root表示后序遍历的根节点，index表示当前的根结点在二叉树层序遍历中所对应的下标（从0开始）。寻找根结点root在中序遍历中的位置i以区分左右子树的位置。然后再对左右子树进行层序遍历，左孩子为2*index + 1，右孩子为2*index + 2。
AC代码：
#include <bits/stdc++.h>
using namespace std;
vector<int> in,post,level(1e5,-1);
void levelorder(int root,int start,int end,int index)
{
if(start > end) return ;
int i = start;
while(i < end && in[i] != post[root]) i++;
level[index] = post[root];
levelorder(root-1-end+i, start, i-1, 2*index+1);
levelorder(root-1, i+1, end, 2*index+2);
}
int main()
{
int N;
cin >> N;
in.resize(N);
post.resize(N);
for(int i = 0; i < N; i++)
{
cin >> post[i];
}
for(int i = 0; i < N; i++)
{
cin >> in[i];
}
levelorder(N-1,0,N-1,0);
bool isVirgin = true;
for(int i = 0; i < level.size(); i++)
{
if(level[i] != -1)
{
if(isVirgin)
{
cout << level[i];
isVirgin = false;
}
else
{
cout << " " << level[i];
}
}
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-03-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录