当前位置:网站首页>PTA 天梯赛练习题集 L2-004 搜索树判断
PTA 天梯赛练习题集 L2-004 搜索树判断
2022-07-07 00:27:00 【qascetic】
搜索树判断
对于二叉搜索树,我们规定任一结点的左子树仅包含严格小于该结点的键值,而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树,得到的树叫做镜像二叉搜索树。
现在我们给出一个整数键值序列,请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列,如果是,则输出对应二叉树的后序遍历序列。
输入格式:
输入的第一行包含一个正整数N(≤1000),第二行包含N个整数,为给出的整数键值序列,数字间以空格分隔。
输出格式:
输出的第一行首先给出判断结果,如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列,则输出YES,否侧输出NO。如果判断结果是YES,下一行输出对应二叉树的后序遍历序列。数字间以空格分隔,但行尾不能有多余的空格。
输入样例1:
7
8 6 5 7 10 8 11
输出样例1:
YES
5 7 6 8 11 10 8
输入样例2:
7
8 6 8 5 10 9 11
输出样例2:
NO
思路:前序遍历结果的特点是第一个为根节点,然后是左子树和右子树。二叉搜索树前序遍历的特点是根节点,比左子树大,比右子树小,用两个变量在需要确定结果的数组上从左到右遍历和从右到左遍历,找到当前根的右孩子和左孩子的两个区间,看区间的差是否为1。正常搜索树是 左孩子区间, 右孩子区间,然后再有一个根。所以左右孩子区间就是相差这一个根区间也就是差1。区间差1符合条件的话那就是前序遍历的搜索树。镜像的话大于左子树小于右子树换一下就行。
如图,二叉搜索树有根节点和左孩子区间右孩子区间。右孩子和左孩子区间相差一。例如图中数字7和数字10就是两个孩子节点的接触区,7在下标为3的位置,10在下标为4的位置,刚好差一,用这个特性就可以判断是不是二叉搜索树了。
AC代码(C++)
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1010; // 最大数
int ismirr; // 标记是否是镜像树
int treeData[MAXN]; // 保存树的前序遍历数据
vector<int>vTreeData; // 保存树的后序遍历数据
void findNode(int Left, int right)
{
if (Left > right) // 区间左必须小于右边否则结束
return;
// 当前循环中Left为次块的根节点
int tempRoot = Left;
// 前序遍历的特点:根 左 右,所以从根右边找孩子节点
// 因此寻找区间是根的下一位(tempRoot + 1)到最后(right)
int tempLeft = tempRoot + 1, tempRight = right;
if (!ismirr) // 非镜像树左<右
{
while (tempLeft <= right && treeData[tempLeft] < treeData[tempRoot])
tempLeft++;
while (tempRight > Left && treeData[tempRight] >= treeData[tempRoot])
tempRight--;
}
else // 镜像树右>左
{
while (tempLeft <= right && treeData[tempLeft] >= treeData[tempRoot])
tempLeft++;
while (tempRight > Left && treeData[tempRight] < treeData[tempRoot])
tempRight--;
}
// 区间左右非1就不符合条件
if (tempLeft - tempRight != 1)
return;
// 根据分割的区间继续递归寻找,这两个函数不可以更换位置
// 因为后序遍历需要左 右 根
findNode(Left + 1, tempRight);
findNode(tempLeft, right);
// 左 右 根 所以直接把找到的元素放入容器即可,就是符合后续便利
vTreeData.push_back(treeData[Left]);
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> treeData[i];
ismirr = false; // 假设为非镜像树
findNode(0, n - 1);
// 容器元素小于输入的元素数量说明不服和搜索树遍历条件
// 但是也有可能是镜像树的原因所以镜像树方式也判断一下
if (vTreeData.size() != n)
{
ismirr = true; // 标记为镜像树
vTreeData.clear(); // 清空容器
findNode(0, n - 1);
}
// 两轮判断都是不符合条件那么就更本不是搜索树
if (vTreeData.size() != n)
cout << "NO\n";
else
{
// 符合条件按照格式输出即可
cout << "YES\n";
for (int i = 0; i < n; i++)
{
// 直接输出容器里的内容因为容器内部就是后序遍历的结果
cout << vTreeData[i];
if (i == (n - 1))
cout << endl;
else
cout << " ";
}
}
return 0;
}
边栏推荐
- Things about data storage 2
- 得物客服一站式工作台卡顿优化之路
- 什么是消息队列?
- Distributed global ID generation scheme
- Paper reading [semantic tag enlarged xlnv model for video captioning]
- 京东商品详情页API接口、京东商品销量API接口、京东商品列表API接口、京东APP详情API接口、京东详情API接口,京东SKU信息接口
- WEB架构设计过程
- 5阶多项式轨迹
- Leetcode: maximum number of "balloons"
- Pinduoduo product details interface, pinduoduo product basic information, pinduoduo product attribute interface
猜你喜欢
How digitalization affects workflow automation
【日常训练--腾讯精选50】235. 二叉搜索树的最近公共祖先
Web Authentication API兼容版本信息
Simple case of SSM framework
毕业之后才知道的——知网查重原理以及降重举例
[binary tree] binary tree path finding
Digital IC interview summary (interview experience sharing of large manufacturers)
分布式全局ID生成方案
[PM products] what is cognitive load? How to adjust cognitive load reasonably?
What is message queuing?
随机推荐
Mysql-centos7 install MySQL through yum
What is message queuing?
SQL query: subtract the previous row from the next row and make corresponding calculations
Harmonyos practice - Introduction to development, analysis of atomized services
5. 数据访问 - EntityFramework集成
Mybaits multi table query (joint query, nested query)
Tablayout modification of customized tab title does not take effect
产业金融3.0:“疏通血管”的金融科技
Hcip seventh operation
Introduction to distributed transactions
Go 语言的 Context 详解
What are the common message queues?
数字IC面试总结(大厂面试经验分享)
微信小程序蓝牙连接硬件设备并进行通讯,小程序蓝牙因距离异常断开自动重连,js实现crc校验位
消息队列:重复消息如何处理?
Type de texte de commutation d'entrée et de mot de passe de l'applet natif
Paper reading [semantic tag enlarged xlnv model for video captioning]
【已解决】记一次EasyExcel的报错【读取xls文件时全表读不报错,指定sheet名读取报错】
Leetcode: maximum number of "balloons"
Realize GDB remote debugging function between different network segments