首页 > 代码库 > PAT L2-004. 这是二叉搜索树吗?
PAT L2-004. 这是二叉搜索树吗?
题目链接:PAT L2-004. 这是二叉搜索树吗?
题意:
给你一串数,问你是否是一个二叉搜索树或者是镜像的先序遍历。
如果是,就输出这棵树的后序遍历。
题解:
根据二叉搜索树的性质,模拟判断一下。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 const int N=1e4+7; 6 7 int n,ismirror; 8 vector<int>pre,ans; 9 10 void dfs(int l,int r) 11 { 12 if(r<l)return; 13 int i=r,j=l+1; 14 if(ismirror) 15 { 16 while(i>l&&pre[l]>pre[i])i--; 17 while(j<=r&&pre[l]<=pre[j])j++; 18 }else 19 { 20 while(i>l&&pre[l]<=pre[i])i--; 21 while(j<=r&&pre[l]>pre[j])j++; 22 } 23 if(j-i!=1)return; 24 dfs(l+1,i),dfs(j,r); 25 ans.push_back(pre[l]); 26 } 27 28 int main() 29 { 30 scanf("%d",&n); 31 F(i,1,n) 32 { 33 int x; 34 scanf("%d",&x); 35 pre.push_back(x); 36 } 37 dfs(0,n-1); 38 if(ans.size()!=n)ismirror=1,ans.clear(),dfs(0,n-1); 39 if(ans.size()==n) 40 { 41 puts("YES"); 42 for(int i=0;i<n;i++)printf("%d%c",ans[i]," \n"[i==n-1]); 43 }else puts("NO"); 44 return 0; 45 }
PAT L2-004. 这是二叉搜索树吗?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。