【2020HBU天梯赛训练】7-28 搜索树判断
借鉴柳神做法，不用生成树
7-28 搜索树判断
对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。
现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。
输入格式:
输入的第一行包含一个正整数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边判断 边把根存进去。后序遍历方法存入数组。
使用isMirror进行两次判断。
用根root 和边界值尾下标tail进行判断是否满足搜索树条件。
#include<iostream>
#include<vector>
using namespace std;
vector<int>num;
vector<int>nn;
bool isMirror = false;
void getpose(int root,int tail){
if(root > tail)return;
int i = root+1, j = tail;
if(!isMirror){
while(i <= tail && num[root] > num[i]) i++;
while(j > root && num[root] <= num[j]) j--;
}else{
while(i <= tail && num[root] <= num[i]) i++;
while(j > root && num[root] > num[j]) j--;
}if(i-j != 1)return;
getpose(root+1,j);
getpose(i,tail);
nn.push_back(num[root]);
}
int main(){
int n;
cin>>n;
num.resize(n);
for(int i=0;i<n;i++)cin>>num[i];
getpose(0,n-1);
if(nn.size()!=n){
isMirror = true;
nn.clear();
getpose(0, n-1);
}
if(nn.size() == n){
printf("YES\n%d",nn[0]);
for(int i=1;i<n;i++)cout<<" "<<nn[i];
}else cout<<"NO";
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/01/31 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
