当前位置:网站首页>L2-006 tree traversal (25 points)
L2-006 tree traversal (25 points)
2022-07-06 11:26:00 【%xiao Q】
subject
Given a binary tree's post order traversal and middle order traversal , Please output the sequence of its sequence traversal . It is assumed that the key values are all positive integers which are not equal to each other .
Input format :
The first line of input gives a positive integer N(≤30), Is the number of nodes in a binary tree . The second line gives the sequence of traversal . The third line gives the order traversal sequence . Numbers are separated by spaces .
Output format :
Output the sequence traversal sequence of the tree in one line . Between the numbers 1 Space separation , There must be no extra space at the beginning and end of the line .
sample input :
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
sample output :
4 1 6 3 5 7 2
analysis
In this problem, we need to know how to build a tree when we know the middle order traversal and post order traversal of a binary tree , Here we can do this , The last node of subsequent traversal must be the root node , Then find the node in the middle order traversal , According to the characteristics of the middle order traversal, the left and right subtrees can be separated , Then in recursive left subtree and with subtree , Do the same thing .
Then there is program traversal , It's directly used here bfs Search it .
Reference code :
#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];
// Build up trees
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;
// Must recurse right subtree first , Because some points in front of the root node of subsequent traversal must be points of the right subtree ,
// And we are looking for recursion according to the root section of subsequent traversal moving forward gradually
creat(mid + 1, inr, 2 * u + 1);
creat(inl, mid - 1, 2 * u);
}
// Sequence traversal
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;
}
边栏推荐
- Use dapr to shorten software development cycle and improve production efficiency
- QT creator specifies dependencies
- L2-001 紧急救援 (25 分)
- Principes JDBC
- AcWing 1294. Cherry Blossom explanation
- Remember a company interview question: merge ordered arrays
- Windows下安装MongDB教程、Redis教程
- 02-项目实战之后台员工信息管理
- Record a problem of raspberry pie DNS resolution failure
- Django运行报错:Error loading MySQLdb module解决方法
猜你喜欢
Picture coloring project - deoldify
How to configure flymcu (STM32 serial port download software) is shown in super detail
打开浏览器的同时会在主页外同时打开芒果TV,抖音等网站
Install mongdb tutorial and redis tutorial under Windows
Use dapr to shorten software development cycle and improve production efficiency
[free setup] asp Net online course selection system design and Implementation (source code +lunwen)
[Blue Bridge Cup 2017 preliminary] grid division
Deoldify项目问题——OMP:Error#15:Initializing libiomp5md.dll,but found libiomp5md.dll already initialized.
PHP - whether the setting error displays -php xxx When PHP executes, there is no code exception prompt
[download app for free]ineukernel OCR image data recognition and acquisition principle and product application
随机推荐
[download app for free]ineukernel OCR image data recognition and acquisition principle and product application
[Blue Bridge Cup 2017 preliminary] grid division
快来走进JVM吧
MySQL的一些随笔记录
自动机器学习框架介绍与使用(flaml、h2o)
[蓝桥杯2020初赛] 平面切分
Nanny level problem setting tutorial
How to build a new project for keil5mdk (with super detailed drawings)
软件测试-面试题分享
AcWing 1298. Solution to Cao Chong's pig raising problem
[AGC009D]Uninity
[ahoi2009]chess Chinese chess - combination number optimization shape pressure DP
Pytorch基础
记一次某公司面试题:合并有序数组
Neo4j installation tutorial
Database advanced learning notes -- SQL statement
Image recognition - pyteseract TesseractNotFoundError: tesseract is not installed or it‘s not in your path
图片上色项目 —— Deoldify
Are you monitored by the company for sending resumes and logging in to job search websites? Deeply convinced that the product of "behavior awareness system ba" has not been retrieved on the official w
Windows下安装MongDB教程、Redis教程