QQ扫一扫联系
（笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点，每个节点的权值都大雨父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。现输入序列的规模n（1≤n<100）和序列的 n 个元素，试求其对应的笛卡尔树的深度 d（根节点深度为1），以及有多少个叶子节点的深度为d。
#include<iostream>
using namespace std;
const int SIZE=100+5;
const int INFINITY=1000000;
int n,a[SIZE],maxDeep,num;
void solve(int left,int right,int deep)
{
int i,j,min;
if(deep>maxDeep){
maxDeep=deep;
num=1;
}
else if(deep==maxDeep)
① ;
min= INFINITY;
for(i=left;i<=right;i++)
if(min>a[i]){
min=a[i];
② ;
}
if(left<j)
③ ;
if(j<right)
④ ;
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
maxDeep=0;
solve(1,n,1);
cout<<maxDeep<<' '<<num<<endl;
return 0;
}
