笛卡尔树(Cartesian tree)

数据结构与算法第四章树(tree) 笛卡尔树(Cartesian tree)

适用组别：提高组
难度系数：7

P5854

笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点，每个节点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。笛卡尔树也可以是最大堆，逻辑相应改变。

笛卡尔树是一棵二叉树，树的每个节点有两个值，一个为key，一个为value。光看key的话，笛卡尔树是一棵二叉搜索树，每个节点的左子树的key都比它小，右子树都比它大；光看value的话，笛卡尔树有点类似堆，根节点的value是最小的，每个节点的value都比它的子树要小。

例题：
下图就是一棵对应的笛卡尔树。现输入序列的规模n(1≤n<100) 和序列的 n 个元素，试求其对应的笛卡尔树的深度 d（根节点深度为 1），以及有多少个叶子节点的深度为 d。

实例序列：
7 2 12 1 10 5 15 3

代码实现：

/**************************************************************** 
 * Description: C++ implementation of  Cartesian tree  笛卡尔树
 * Author: Alex Li
 * Date: 2023-07-06 13:02:29
 * LastEditTime: 2023-07-06 13:11:50
****************************************************************/

#include <iostream>
using namespace std;
const int SIZE=100;
const int INFINITY=100000;
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)num++;
    min=INFINITY;
    for ( i =left; i <=right; i++)
        if(min>a[i]){
            min=a[i];
            j=i;
        }
        if(left<j)Solve(left,j-1,deep+1);
        if(j<right)Solve(j+1,right,deep+1);
}

int main(){
    cin>>n;
    for (int i =1; i <=n; i++)
        cin>>a[i];
    maxDeep=0;
    Solve(1,n,1);
    cout<<maxDeep<<' '<<num<<endl;
    
}

/*
intput:
8   
7 2 12 1 10 5 15 3 
output:
4 2 
*/

I4585