1043 Is It a Binary Search Tree (25 分)(二叉查找树)
2024-09-02 01:53:18
#include<bits/stdc++.h> using namespace std;
typedef struct node;
typedef node *tree;
struct node
{
int data;
tree L,R;
};
void Insert(tree &bt,int x)
{
if(bt==NULL){
bt=new node;
bt->data=x;
bt->L=NULL;
bt->R=NULL;
return;
}
if(x<bt->data) Insert(bt->L,x);
else Insert(bt->R,x);
}
vector<int>pre1,pre2,post1,post2;
void preorder1(tree bt,vector<int>&p)
{
if(bt){
p.push_back(bt->data);
preorder1(bt->L,p);
preorder1(bt->R,p);
}
}
void preorder2(tree bt,vector<int>&p)
{
if(bt){
p.push_back(bt->data);
preorder2(bt->R,p);
preorder2(bt->L,p); }
} void postorder1(tree bt,vector<int>&p)
{
if(bt){
postorder1(bt->L,p);
postorder1(bt->R,p);
p.push_back(bt->data);
}
} void postorder2(tree bt,vector<int>&p)
{
if(bt){
postorder2(bt->R,p);
postorder2(bt->L,p);
p.push_back(bt->data);
}
}
int main()
{
int n;
scanf("%d",&n);
tree bt;
bt=NULL;
vector<int>tt;
for(int i=;i<n;i++){
int x;
scanf("%d",&x);
tt.push_back(x);
Insert(bt,x);
}
preorder1(bt,pre1);
preorder2(bt,pre2);
postorder1(bt,post1);
postorder2(bt,post2);
if(tt==pre1){
puts("YES");
for(int i=;i<post1.size();i++){
if(i) printf(" ");
printf("%d",post1[i]);
}
}
else if(tt==pre2){
puts("YES");
for(int i=;i<post2.size();i++){
if(i) printf(" ");
printf("%d",post2[i]);
}
}
else{
puts("NO");
}
return ;
}
最新文章
- Java 并发和多线程(三) 多线程的代价 [转]
- node相关的精典材料
- 通过批处理(bat)命令创建mysql数据库及用户等
- UML图示与代码对照
- 大型网站用什么技术比较好,JSP,PHP,ASP.NET
- NDK开发之获得域和方法描述符
- Page.ClientScript.RegisterStartupScript不执行问题
- ADT 连接手机运行android应用程序时报错
- mysql快速翻页查询方法
- 在IDEA中实战Git(转载自)
- django中数据库操作——in操作符
- 移动前端的html5 head 头标签
- Yii2 mongoDb的配置及使用
- nmap扫描出现tcpwrapped
- #Python学习#python虚拟环境——virtualenv
- SpagoBI 论坛
- RobotFramework自动化4-批量操作案例
- SQLServer中数据加密方法
- 【尺取法好题】POJ2566-Bound Found
- Python to list users in AWS