这是二叉搜索树吗?(二叉搜索树性质)

这是二叉搜索树吗?(二叉搜索树性质)

 

 AC_Code:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1e3+10;
 5 
 6 //如果是二叉搜索树(左小右大)剩下的所有点中间一定可以找到一个分界线使左边的所有点比第一个点(即根节点)小,右边的大。
 7 //e.g 4 1 3 2 6 5 7 -->4   1 3 2   6 5 7
 8 
 9 int n;
10 int a[maxn];
11 bool isMirror;
12 vector<int>v;
13 
14 void dfs(int left, int right){
15     if( left>right ) return ;
16     int i=left+1, j=right;
17     if( !isMirror ){
18         while( i<=j && a[i]<a[left] ) i++;
19         while( j>left && a[j]>=a[left] ) j--;
20     }else{
21         while( i<=j && a[i]>=a[left] ) i++;
22         while( j>left && a[j]<a[left] ) j--;
23     }
24     if( i-j!=1 ) return ;
25     dfs(left+1,j);
26     dfs(i,right);
27     v.push_back(a[left]);
28 }
29 int main()
30 {
31     scanf("%d",&n);
32     for(int i=1;i<=n;i++){
33         scanf("%d",&a[i]);
34     }
35     dfs(1,n);
36     int _size = v.size();
37     if( _size<n ){
38         isMirror = true;
39         v.clear();
40         dfs(1,n);
41         _size = v.size();
42     }
43 
44     if( _size==n ){
45         printf("YES
%d",v[0]);
46         for(int i=1;i<_size;i++){
47             printf(" %d",v[i]);
48         }
49         printf("
");
50     }else{
51         printf("NO
");
52     }
53 
54     return 0;
55 }
原文地址:https://www.cnblogs.com/wsy107316/p/14024684.html