当前位置:网站首页>PTA ladder game exercise set l2-004 search tree judgment
PTA ladder game exercise set l2-004 search tree judgment
2022-07-07 05:52:00 【qascetic】
Search tree judgment
For binary search trees , We stipulate that the left subtree of any node contains only the key values which are strictly smaller than the node , And its right subtree contains the key value greater than or equal to the node . If we swap the left and right subtrees of each node , The resulting tree is called a mirror binary search tree .
Now let's give a sequence of integer key values , Please write a program to judge whether the sequence is a preorder traversal sequence of a binary search tree or a mirror binary search tree , If it is , Then output the post order traversal sequence of the corresponding binary tree .
Input format :
The first line of input contains a positive integer N(≤1000), The second line contains N It's an integer , For the given sequence of integer key values , Numbers are separated by spaces .
Output format :
The first line of the output first gives the judgment result , If the input sequence is the preorder traversal sequence of a binary search tree or a mirror binary search tree , The output YES, No side output NO. If it turns out that YES, The next line outputs the post order traversal sequence of the corresponding binary tree . Numbers are separated by spaces , But there can't be extra spaces at the end of the line .
sample input 1:
7
8 6 5 7 10 8 11
sample output 1:
YES
5 7 6 8 11 10 8
sample input 2:
7
8 6 8 5 10 9 11
sample output 2:
NO
Ideas : The characteristic of the preorder traversal result is that the first is the root node , Then left subtree and right subtree . The characteristic of preorder traversal of binary search tree is the root node , Larger than the left subtree , Smaller than the right subtree , Use two variables to traverse left to right and right to left on the array that needs to determine the result , Find the two intervals of the right child and the left child of the current root , See whether the difference of the interval is 1. The normal search tree is Left child interval , Right child interval , Then there is another root . So the left and right children's interval is the difference. This root interval is also the difference 1. Interval difference 1 If it meets the conditions, it is the search tree traversed by the previous order . If the image is larger than the left subtree and smaller than the right subtree, just change .
Pictured , The binary search tree has a root node and a left child interval and a right child interval . The difference between the right child and the left child is one . For example, the number in the figure 7 And number 10 It is the contact area of two child nodes ,7 The subscript for 3 The location of ,10 The subscript for 4 The location of , It's just one , With this feature, you can judge whether it is a binary search tree .
AC Code (C++)
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1010; // The maximum number
int ismirr; // Mark whether it is a mirror tree
int treeData[MAXN]; // Save the pre order traversal data of the tree
vector<int>vTreeData; // Save the post order traversal data of the tree
void findNode(int Left, int right)
{
if (Left > right) // The left side of the interval must be less than the right side, otherwise it ends
return;
// In the current loop Left Is the root node of the secondary block
int tempRoot = Left;
// Characteristics of preorder traversal : root Left Right , So find the child node from the right side of the root
// So looking for an interval is next to the root (tempRoot + 1) In the end (right)
int tempLeft = tempRoot + 1, tempRight = right;
if (!ismirr) // Non mirrored tree left < Right
{
while (tempLeft <= right && treeData[tempLeft] < treeData[tempRoot])
tempLeft++;
while (tempRight > Left && treeData[tempRight] >= treeData[tempRoot])
tempRight--;
}
else // Image tree right > Left
{
while (tempLeft <= right && treeData[tempLeft] >= treeData[tempRoot])
tempLeft++;
while (tempRight > Left && treeData[tempRight] < treeData[tempRoot])
tempRight--;
}
// The left and right of the interval are not 1 They don't meet the requirements
if (tempLeft - tempRight != 1)
return;
// Continue to search recursively according to the segmented interval , These two functions cannot be replaced
// Because post order traversal requires left Right root
findNode(Left + 1, tempRight);
findNode(tempLeft, right);
// Left Right root So just put the found elements into the container , It is in line with the convenience of follow-up
vTreeData.push_back(treeData[Left]);
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> treeData[i];
ismirr = false; // Assume a non mirrored tree
findNode(0, n - 1);
// The container element is smaller than the number of input elements, indicating that it does not comply with the search tree traversal conditions
// But it may also be the reason for the mirror tree, so judge the mirror tree method
if (vTreeData.size() != n)
{
ismirr = true; // Mark as mirror tree
vTreeData.clear(); // Empty the container
findNode(0, n - 1);
}
// If the two rounds of judgment are not qualified, then it is not a search tree
if (vTreeData.size() != n)
cout << "NO\n";
else
{
// If it meets the conditions, output it in the format
cout << "YES\n";
for (int i = 0; i < n; i++)
{
// Directly output the contents of the container, because the container is the result of post order traversal
cout << vTreeData[i];
if (i == (n - 1))
cout << endl;
else
cout << " ";
}
}
return 0;
}
边栏推荐
- Flinksql read / write PgSQL
- Web authentication API compatible version information
- Distributed global ID generation scheme
- Common skills and understanding of SQL optimization
- Flask1.1.4 Werkzeug1.0.1 源码分析:启动流程
- Why does the data center need a set of infrastructure visual management system
- Realize GDB remote debugging function between different network segments
- 集群、分布式、微服务的区别和介绍
- Message queue: how to deal with message backlog?
- Nvisual network visualization
猜你喜欢
Add salt and pepper noise or Gaussian noise to the picture
pytorch_ 01 automatic derivation mechanism
Nvisual network visualization
Industrial Finance 3.0: financial technology of "dredging blood vessels"
分布式事务解决方案之2PC
如何提高网站权重
Harmonyos practice - Introduction to development, analysis of atomized services
Three level menu data implementation, nested three-level menu data
Reading notes of Clickhouse principle analysis and Application Practice (6)
Distributed global ID generation scheme
随机推荐
[daily training -- Tencent selected 50] 235 Nearest common ancestor of binary search tree
线性回归
Reading notes of Clickhouse principle analysis and Application Practice (6)
Red Hat安装内核头文件
SAP ABAP BDC (batch data communication) -018
2pc of distributed transaction solution
AI人脸编辑让Lena微笑
Things about data storage 2
Question 102: sequence traversal of binary tree
Mybaits multi table query (joint query, nested query)
PTA 天梯赛练习题集 L2-003 月饼 测试点2,测试点3分析
Web Authentication API兼容版本信息
Sidecar mode
产业金融3.0:“疏通血管”的金融科技
How to get free traffic in pinduoduo new store and what links need to be optimized in order to effectively improve the free traffic in the store
Nvisual network visualization
Flink SQL realizes reading and writing redis and dynamically generates hset key
Taobao commodity details page API interface, Taobao commodity list API interface, Taobao commodity sales API interface, Taobao app details API interface, Taobao details API interface
Codeforces Round #416 (Div. 2) D. Vladik and Favorite Game
如何提高网站权重