NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 28 题

2.（笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点，每个节点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列 $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);
    co

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

笛卡尔树是一棵同时满足"中序遍历=原序列"和"最小堆性质"的二叉树。算法本质是分治：在区间[left,right]中找到最小值作为根，递归处理左右子区间。计算深度时用deep参数记录当前深度，遇到更深节点更新maxDeep并将叶子计数num重置为1；深度相同时num++。

易错1：题目求的是"叶子节点的深度为d"，不是"所有节点的深度为d"。只有没有子节点的节点（即区间长度为1的递归基）才是叶子。易错2：num=1是在发现更大深度时重置，不是累加；只有deep==maxDeep时才num++。易错3：min初始化为INFINITY后，找到最小值时记住下标j=i。如果最小值出现在最左侧(left=j)则无左子树，出现在最右侧(j=right)则无右子树。

心算技巧

手算示例：序列[7,2,12,1,10,5,15,3]

• 全局最小值=1（下标4）=根节点
• 左子区间[7,2,12]最小值=2（下标2）=左子树根
• 右子区间[10,5,15,3]最小值=3（下标8）=右子树根
• 递归构建得到树形结构，计算各节点深度

快速验证：根深度1，左右子树根深度2，叶子位于最深深度。

符号释义