当前位置:网站首页>Informatics Orsay all in one 1339: [example 3-4] find the post order traversal | Valley p1827 [usaco3.4] American Heritage
Informatics Orsay all in one 1339: [example 3-4] find the post order traversal | Valley p1827 [usaco3.4] American Heritage
2022-07-05 20:18:00 【Jun Yi_ noip】
【 Topic link 】
ybt 1339:【 example 3-4】 To find the subsequent traversal
Luogu P1827 [USACO3.4] American blood American Heritage
Both questions are known preorder and middle order ergodic sequences , Find the postorder traversal sequence
The difference for :【ybt 1339】 First enter the preorder traversal sequence , Then enter the middle order traversal sequence .【 Luogu P1827】 First enter the middle order traversal sequence , Then enter the preorder traversal sequence .
【 Topic test site 】
1. Binary tree
We know the antecedent 、 Middle order side path sequence , Find the postorder traversal sequence
【 Their thinking 】
solution 1:
Suppose the input middle order traversal sequence is :DBAECH, The preorder traversal sequence is ABDCEF. Take this input as an example to discuss the solution of the problem .
The current problem to be solved is : We know the antecedent 、 Middle order traversal sequence , Building a binary tree .
- First, the first letter in the preorder traversal is the value of the root node of the tree (A).
- Then find the root node value in the middle order traversal sequence (A) The location of , The sequence to the left of the root value (DB) Is the middle order traversal sequence of the left subtree of the root node . The sequence to the right of the root value (ECF) Is the middle order traversal sequence of the right subtree of the root node .
- In the preorder traversal sequence, the length of the sequence traversed according to the order in the left subtree , Find the preorder traversal sequence of the left subtree (BD), And the preorder traversal sequence of the right subtree (CEF).
- Recursively call “ Known preorder in order traversal sequence to find binary tree ” Function of . Now we know the left subtree of the root node 、 Preorder of right subtree 、 Middle order traversal sequence , Then the left subtree and right subtree of the root node can be constructed ( Building subtrees is relative to building A A tree that is the root node , It's a small-scale problem , When solving large-scale problems recursively , The solution of the small-scale problem is considered to be known )
- With A Is the root node , Connect the constructed left and right subtrees , That is, the construction of the tree is completed .
Next, do post order traversal of this tree , You can get the post order traversal sequence of the tree .
How to write it 1: Use character array
Enter the sequence of first order traversal to s_pre, Middle order traversal sequence to character array s_in.
function createTree Need to ml,mr,pl,pr, Meaning for : By a priori sequence s_pre[pl]~s_pre[pr]
And middle order sequence s_in[ml]~s_in[mr]
Construct a binary tree
According to the above algorithm , First, find the first character of the sequence in the middle sequence s_pre[pl]
The location of , Find the location for i. Then the middle order traversal sequence of the left subtree is s_in[ml]~s_in[i-1]
, The length is i-ml, In the preorder traversal sequence , from pl+1 Start with the length i-ml Sequence , The position of the last element is pl+i-ml, Then the preorder traversal sequence of the left subtree is s_pre[pl+1]~s_pre[pl+i-ml]
. Similarly , The middle order sequence of the right subtree can be obtained as s_in[i+1]~s_in[mr]
, The precedence sequence is s_pre[pl+i-ml+1]~s_pre[pr]
.
Use createTree Generate left and right subtrees respectively , Next to the newly assigned root node , You get this tree .
The recursive exit is : The subscript range of preorder and middle order sequences must have pl<=pr
And ml<=mr
, If this condition is not met , Sequence range is meaningless , Should return to .
How to write it 2: Use string class
The idea is similar to the above method , I won't repeat .
Use string class , have access to substr Member function to get substring . The sequence of each incoming function 、 Middle order sequences are string Class object .
【 Solution code 】:ybt 1339:【 example 3-4】 To find the subsequent traversal
How to write it 1: Use character array
#include <bits/stdc++.h>
using namespace std;
#define N 1000
struct Node
{
char val;
int left, right;
};
Node node[N];
int p = 1;
char s_pre[105], s_in[105];//s_pre: First, we traverse the sequence s_in: Middle order traversal sequence
// By a priori sequence s_pre[pl]~s_pre[pr] And middle order sequence s_in[ml]~s_in[mr] Construct a binary tree , Return to root node
int createTree(int pl, int pr, int ml, int mr)
{
if(pl > pr || ml > mr)
return 0;
int np = p++, i;
node[np].val = s_pre[pl];
for(i = ml; i <= mr; ++i)
{
if(s_in[i] == s_pre[pl])
break;
}
node[np].left = createTree(pl + 1, pl + i - ml, ml, i - 1);
node[np].right = createTree(pl + i - ml + 1, pr, i + 1, mr);
return np;
}
void postOrder(int root)
{
if(root != 0)
{
postOrder(node[root].left);
postOrder(node[root].right);
cout << node[root].val;
}
}
int main()
{
cin >> s_pre >> s_in;
int root = createTree(0, strlen(s_pre) - 1, 0, strlen(s_in) - 1);
postOrder(root);
return 0;
}
How to write it 2: Use string class
#include <bits/stdc++.h>
using namespace std;
#define N 1000
struct Node
{
char val;
int left, right;
};
Node node[N];
int p = 1;
string s_pre, s_in;
int createTree(string sp, string si)// Using a preorder sequence sp And middle order sequence si Building a binary tree , Return to tree root
{
int np = p++, i;
node[np].val = sp[0];
for(i = 0; i < si.length(); ++i)
{
if(sp[0] == si[i])
break;
}
int len_l = i, len_r = si.length() - 1 - i;// The sequence length of left and right subtrees
if(len_l > 0)// The sequence length is greater than 0, To build a tree
node[np].left = createTree(sp.substr(1, len_l), si.substr(0, len_l));
if(len_r > 0)
node[np].right = createTree(sp.substr(i+1, len_r), si.substr(i+1, len_r));
return np;
}
void postOrder(int root)
{
if(root != 0)
{
postOrder(node[root].left);
postOrder(node[root].right);
cout << node[root].val;
}
}
int main()
{
cin >> s_pre >> s_in;
int root = createTree(s_pre, s_in);
postOrder(root);
return 0;
}
【 Solution code 】: Luogu P1827 [USACO3.4] American blood American Heritage
How to write it 1: Use character array
#include <bits/stdc++.h>
using namespace std;
#define N 1000
struct Node
{
char val;
int left, right;
};
Node node[N];
int p = 1;
char s_pre[105], s_in[105];//s_pre: First, we traverse the sequence s_in: Middle order traversal sequence
// By a priori sequence s_pre[pl]~s_pre[pr] And middle order sequence s_in[ml]~s_in[mr] Construct a binary tree , Return to root node
int createTree(int pl, int pr, int ml, int mr)
{
if(pl > pr || ml > mr)
return 0;
int np = p++, i;
node[np].val = s_pre[pl];
for(i = ml; i <= mr; ++i)
{
if(s_in[i] == s_pre[pl])
break;
}
node[np].left = createTree(pl + 1, pl + i - ml, ml, i - 1);
node[np].right = createTree(pl + i - ml + 1, pr, i + 1, mr);
return np;
}
void postOrder(int root)
{
if(root != 0)
{
postOrder(node[root].left);
postOrder(node[root].right);
cout << node[root].val;
}
}
int main()
{
cin >> s_in >> s_pre;
int root = createTree(0, strlen(s_pre) - 1, 0, strlen(s_in) - 1);
postOrder(root);
return 0;
}
How to write it 2: Use string class
#include <bits/stdc++.h>
using namespace std;
#define N 1000
struct Node
{
char val;
int left, right;
};
Node node[N];
int p = 1;
string s_pre, s_in;
int createTree(string sp, string si)// Using a preorder sequence sp And middle order sequence si Building a binary tree , Return to tree root
{
int np = p++, i;
node[np].val = sp[0];
for(i = 0; i < si.length(); ++i)
{
if(sp[0] == si[i])
break;
}
int len_l = i, len_r = si.length() - 1 - i;// The sequence length of left and right subtrees
if(len_l > 0)// The sequence length is greater than 0, To build a tree
node[np].left = createTree(sp.substr(1, len_l), si.substr(0, len_l));
if(len_r > 0)
node[np].right = createTree(sp.substr(i+1, len_r), si.substr(i+1, len_r));
return np;
}
void postOrder(int root)
{
if(root != 0)
{
postOrder(node[root].left);
postOrder(node[root].right);
cout << node[root].val;
}
}
int main()
{
cin >> s_in >> s_pre;
int root = createTree(s_pre, s_in);
postOrder(root);
return 0;
}
边栏推荐
- BZOJ 3747 POI2015 Kinoman 段树
- C - sequential structure
- 字节跳动Dev Better技术沙龙成功举办,携手华泰分享Web研发效能提升经验
- DP: tree DP
- 零道云新UI设计中
- After 95, Alibaba P7 published the payroll: it's really fragrant to make up this
- [quick start of Digital IC Verification] 1. Talk about Digital IC Verification, understand the contents of the column, and clarify the learning objectives
- 【数字IC验证快速入门】2、通过一个SoC项目实例,了解SoC的架构,初探数字系统设计流程
- leetcode刷题:二叉树12(二叉树的所有路径)
- 死信队列入门(两个消费者,一个生产者)
猜你喜欢
走入并行的世界
关于BRAM IP复位的优先级
CTF reverse Foundation
- Oui. Net Distributed Transaction and Landing Solution
Guidelines for application of Shenzhen green and low carbon industry support plan in 2023
JS implementation prohibits web page zooming (ctrl+ mouse, +, - zooming effective pro test)
全国爱眼教育大会,2022第四届北京国际青少年眼健康产业展会
[Yugong series] go teaching course in July 2022 004 go code Notes
Leetcode skimming: binary tree 17 (construct binary tree from middle order and post order traversal sequence)
.Net分布式事務及落地解决方案
随机推荐
BZOJ 3747 POI2015 Kinoman 段树
Solve the problem that the database configuration information under the ThinkPHP framework application directory is still connected by default after modification
E. Singhal and Numbers(质因数分解)
Leetcode: binary tree 15 (find the value in the lower left corner of the tree)
【c语言】快速排序的三种实现以及优化细节
走入并行的世界
Go language | 03 array, pointer, slice usage
July 4, 2022 - July 10, 2022 (UE4 video tutorial MySQL)
Introduction to dead letter queue (two consumers, one producer)
[quick start to digital IC Verification] 8. Typical circuits in digital ICs and their corresponding Verilog description methods
计算lnx的一种方式
Enter the parallel world
【数字IC验证快速入门】6、Questasim 快速上手使用(以全加器设计与验证为例)
【c语言】归并排序
银河证券在网上开户安全吗?
sun. misc. Base64encoder error reporting solution [easy to understand]
Ffplay document [easy to understand]
leetcode刷题:二叉树15(找树左下角的值)
How to retrieve the root password of MySQL if you forget it
Bzoj 3747 poi2015 kinoman segment tree