(笛卡尔树)对于一个给定的两两不等的正整数序列,笛卡尔树是这样的一棵二叉树:首先,它是一个最小堆,即除了根结点,每个节点的权值都大雨父节点的权值;其次,它的中序遍历恰好就是给定的序列。例如,对于序列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)
1;
min = INFINITY;
for (i = left; i <= right; i++)
if (min > a[i]) {
min = a[i];
2;
}
if (left < j)
3;
if (j < right)
4;
}
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;
}