当前位置:网站首页>L2-006 树的遍历 (25 分)
L2-006 树的遍历 (25 分)
2022-07-06 09:14:00 【%xiao Q】
题目
给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数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
分析
这题我们得知道如何在已知二叉树的中序遍历和后序遍历的情况下建树,这里我们可以这样做,后续遍历的最后一个节点一定是根节点,然后在中序遍历中找该节点,根据中序遍历的特性可以分开左右子树,然后在递归左子树和有子树,进行同样的操作。
然后就是程序遍历,这里直接用bfs搜即可。
参考代码:
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++)
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;
const int N = 10010;
int pos, n;
int pre[N], in[N], post[N];
struct node
{
int l, r, w;
}T[N];
// 建树
void creat(int inl, int inr, int u)
{
if(inl > inr) return ;
// puts("hh");
// cout << u << endl;
T[u].w = post[pos--];
T[u].l = 2 * u, T[u].r = 2 * u + 1;
int mid;
for(mid = inl; mid <= inr; mid++)
if(T[u].w == in[mid]) break;
//必须先递归右子树,因为后续遍历的根节点前面一些点一定是右子树的点,
// 而我们是根据后续遍历的根节逐渐前移来去找递归的
creat(mid + 1, inr, 2 * u + 1);
creat(inl, mid - 1, 2 * u);
}
// 进行层序遍历
void bfs()
{
int idx = 0;
queue<int> q;
q.push(1);
while(q.size())
{
node t = T[q.front()];
q.pop();
if(!idx) cout << t.w;
else cout << " " << t.w;
idx++;
if(T[t.l].w != -1) q.push(t.l);
if(T[t.r].w != -1) q.push(t.r);
}
}
int main()
{
cin >> n;
rep(i, 1, n) cin >> post[i];
rep(i, 1, n) cin >> in[i];
memset(T, -1, sizeof T);
pos = n;
creat(1, n, 1);
bfs();
cout << endl;
return 0;
}
边栏推荐
- JDBC原理
- MySQL的一些随笔记录
- 安装numpy问题总结
- Remember the interview algorithm of a company: find the number of times a number appears in an ordered array
- Cookie setting three-day secret free login (run tutorial)
- Solution: log4j:warn please initialize the log4j system properly
- [recommended by bloggers] C # generate a good-looking QR code (with source code)
- CSDN question and answer module Title Recommendation task (II) -- effect optimization
- Use dapr to shorten software development cycle and improve production efficiency
- Error reporting solution - io UnsupportedOperation: can‘t do nonzero end-relative seeks
猜你喜欢
基于apache-jena的知识问答
QT creator runs the Valgrind tool on external applications
Esp8266 at+cipstart= "", "", 8080 error closed ultimate solution
解决安装Failed building wheel for pillow
[download app for free]ineukernel OCR image data recognition and acquisition principle and product application
Did you forget to register or load this tag 报错解决方法
Install mysql5.5 and mysql8.0 under windows at the same time
How to configure flymcu (STM32 serial port download software) is shown in super detail
Detailed reading of stereo r-cnn paper -- Experiment: detailed explanation and result analysis
When you open the browser, you will also open mango TV, Tiktok and other websites outside the home page
随机推荐
AI benchmark V5 ranking
Windows cannot start the MySQL service (located on the local computer) error 1067 the process terminated unexpectedly
There are three iPhone se 2022 models in the Eurasian Economic Commission database
Julia 1.6 1.7 common problem solving
一键提取pdf中的表格
[ahoi2009]chess Chinese chess - combination number optimization shape pressure DP
QT creator uses Valgrind code analysis tool
Why is MySQL still slow to query when indexing is used?
Tcp/ip protocol (UDP)
Test objects involved in safety test
Redis的基础使用
MySQL主从复制、读写分离
neo4j安装教程
Database advanced learning notes -- SQL statement
安装numpy问题总结
When you open the browser, you will also open mango TV, Tiktok and other websites outside the home page
Windows下安装MongDB教程、Redis教程
frp内网穿透那些事
Image recognition - pyteseract TesseractNotFoundError: tesseract is not installed or it‘s not in your path
Invalid global search in idea/pychar, etc. (win10)