当前位置:网站首页>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;
}
边栏推荐
- vs2019 使用向导生成一个MFC应用程序
- Base de données Advanced Learning Notes - - SQL statements
- QT creator specify editor settings
- Mtcnn face detection
- Rhcsa certification exam exercise (configured on the first host)
- Install mongdb tutorial and redis tutorial under Windows
- Error connecting to MySQL database: 2059 - authentication plugin 'caching_ sha2_ The solution of 'password'
- Number game
- Ansible practical series I_ introduction
- [Thesis Writing] how to write function description of jsp online examination system
猜你喜欢
Double to int precision loss
引入了junit为什么还是用不了@Test注解
Windows下安装MongDB教程、Redis教程
一键提取pdf中的表格
02 staff information management after the actual project
QT creator design user interface
QT creator specifies dependencies
MySQL and C language connection (vs2019 version)
Nanny level problem setting tutorial
Deoldify project problem - omp:error 15:initializing libiomp5md dll,but found libiomp5md. dll already initialized.
随机推荐
L2-006 树的遍历 (25 分)
Error reporting solution - io UnsupportedOperation: can‘t do nonzero end-relative seeks
Base de données Advanced Learning Notes - - SQL statements
误删Path变量解决
Face recognition_ recognition
Django running error: error loading mysqldb module solution
Picture coloring project - deoldify
Ansible实战系列一 _ 入门
Introduction to the easy copy module
[ahoi2009]chess Chinese chess - combination number optimization shape pressure DP
TCP/IP协议(UDP)
Learn winpwn (2) -- GS protection from scratch
数据库高级学习笔记--SQL语句
[蓝桥杯2021初赛] 砝码称重
數據庫高級學習筆記--SQL語句
02-项目实战之后台员工信息管理
Julia 1.6 1.7 common problem solving
JDBC原理
[蓝桥杯2017初赛]方格分割
AcWing 1298.曹冲养猪 题解