cdoj 483 Data Structure Problem DFS

题目链接:

http://acm.uestc.edu.cn/#/problem/show/483

题意:

给你n个数，然后这n个数构成的二叉树，是平衡二叉树还是堆

题解:

dfs
根据题目中给的
堆 (a[x]>=a[x*2] && a[x]>=a[x*2+1]) || (a[x]<=a[x*2] && a[x]<=a[x*2+1]) 最大堆最小堆
BST (a[x]大于a[x*2]&& a[x]小于a[x*2+1]) || (a[x]小于a[x*2]&&a[x]大于a[x*2+1]) 平衡二叉树还不会。。是这个条件吗

代码:

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 #define MS(a) memset(a,0,sizeof(a))
  5 #define MP make_pair
  6 #define PB push_back
  7 const int INF = 0x3f3f3f3f;
  8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  9 inline ll read(){
 10     ll x=0,f=1;char ch=getchar();
 11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 13     return x*f;
 14 }
 15 //////////////////////////////////////////////////////////////////////////
 16 const int maxn = 2e5+10;
 17 
 18 int a[maxn];
 19 int flag1,flag2,flag3,flag4;
 20 
 21 void dfs1(int x){
 22     if(flag1 == 0)
 23         return ;
 24 
 25     if(a[x*2]!=0){
 26         if(a[x] >= a[x*2])
 27             dfs1(x*2);
 28         else
 29             flag1 = 0;
 30     }
 31     if(a[x*2+1]!=0){
 32         if(a[x] >= a[x*2+1])
 33             dfs1(x*2+1);
 34         else
 35             flag1 = 0;
 36     }
 37 }
 38 
 39 void dfs2(int x){
 40     if(flag2 == 0)
 41         return ;
 42 
 43     if(a[x*2]!=0){
 44         if(a[x] <= a[x*2])
 45             dfs2(x*2);
 46         else
 47             flag2 = 0;
 48     }
 49     if(a[x*2+1]!=0){
 50         if(a[x] <= a[x*2+1])
 51             dfs2(x*2+1);
 52         else
 53             flag2 = 0;
 54     }
 55 }
 56 
 57 void dfs3(int x){
 58     if(flag3 == 0)
 59         return ;
 60 
 61     if(a[x*2]!=0){
 62         if(a[x]>a[x*2])
 63             dfs3(x*2);
 64         else
 65             flag3 = 0;
 66     }
 67     if(a[x*2+1]!=0){
 68         if(a[x]<a[x*2+1])
 69             dfs3(x*2+1);
 70         else
 71             flag3 = 0;
 72     }
 73 }
 74 
 75 void dfs4(int x){
 76     if(flag4 == 0)
 77         return ;
 78 
 79     if(a[x*2]!=0){
 80         if(a[x]<a[x*2])
 81             dfs4(x*2);
 82         else
 83             flag4 = 0;
 84     }
 85     if(a[x*2+1]!=0){
 86         if(a[x]>a[x*2+1])
 87             dfs4(x*2+1);
 88         else
 89             flag4 = 0;
 90     }
 91 }
 92 
 93 int main(){
 94     int T=read();
 95     for(int cas=1; cas<=T; cas++){
 96         MS(a);
 97         int n=read();
 98         for(int i=1; i<=n; i++)
 99             a[i] = read();
100 
101         flag1=1,flag2=1; // 最大堆 最小堆
102         flag3=1,flag4=1; // 平衡二叉树
103         dfs1(1);
104         dfs2(1);
105         dfs3(1);
106         dfs4(1);
107 
108         if((flag1||flag2) && (flag3||flag4))
109             cout << "Case #" << cas << ": Both
";
110         else if((flag1||flag2) && !(flag3||flag4))
111             cout << "Case #" << cas << ": Heap
";
112         else if(!(flag1||flag2) && (flag3||flag4))
113             cout << "Case #" << cas << ": BST
";
114         else 
115             cout << "Case #" << cas << ": Neither
";
116     }
117 
118     return 0;
119 }