【题目来源】
【题目描述】
笛卡尔树是由一系列不同数字构成的二叉树。
笛卡尔树满足堆的性质，笛卡尔树的中序遍历序列为构建其的原始序列。
最小堆笛卡尔树表示满足小根堆性质的笛卡尔树。
例如，给定序列 {8,15,3,4,1,5,12,10,18,6}，则生成的最小堆笛卡尔树如图所示。
现在，给定一个长度为 N 的原始序列，请你生成最小堆笛卡尔树，并输出其层序遍历序列。
【输入格式】
第一行包含整数 N。
第二行包含 N 个两两不同的整数，表示原始序列。
【输出格式】
共一行，输出最小堆笛卡尔树的层序遍历序列。
【数据范围】
1≤N≤30,
原始序列中元素的取值范围 [−2147483648,2147483647]。
【输入样例】
10
8 15 3 4 1 5 12 10 18 6
【输出样例】
1 3 5 8 4 6 15 10 12 18
【算法分析】
● 笛卡尔树（Cartesian Tree）是由一个序列 a[1], a[2], ..., a[n] 唯一确定的二叉树，其同时满足二叉查找树（BST）性质和堆性质。笛卡尔树的每个结点包含一对儿信息 (pri, val)，其中 pri 固定为元素在原序列中的下标 i，决定了结点在笛卡尔树中的位置。val 为序列元素的值 a[i]，决定了笛卡尔树中结点间的堆序关系。
● 笛卡尔树结构唯一、固定、不可改变
笛卡尔树不是动态平衡树，不支持随意插入或删除操作，只能通过序列重建。只要序列保持不变，对应的笛卡尔树结构就唯一、固定、不可改变。换句话说，笛卡尔树由一个序列唯一确定，不同序列对应不同的笛卡尔树。
● 笛卡尔树（Cartesian Tree）于 1980 年由 Jean Vuillemin 正式提出，其名称源自笛卡尔坐标系。原因在于，笛卡尔树将序列 a[1], a[2], ..., a[n] 中的每个元素 a[i] 映射为笛卡尔坐标系中的点（横坐标 pri = 下标 i, 纵坐标 val = 序列值 a[i]）。
● 笛卡尔树示意图，无法直观体现 val 的具体大小。这是因为，val 是用来 “建造” 笛卡尔树的规则，不是用来 “画在” 笛卡尔树示意图里的数值。
● 笛卡尔树结点纵坐标 val 的差异，不能通过在示意图中把结点 “画得高一点、低一点” 来体现，只靠【谁能当谁的爸爸】来体现。
● 笛卡尔树示意图中，结点的垂直高度（层数）表示结点在树中的深度，仅用于可视化排版。同一层的结点不代表 val 相等，只表示它们在树结构中的层级相同。
● 笛卡尔树满足两条性质：
（1）按 pri 构成二叉搜索树结构，等价于中序遍历结果与原序列完全一致；
（2）按 val 满足堆序关系（小根堆或大根堆）。
简言之，一棵笛卡尔树，pri 决定结点的左右位置，val 决定结点的堆序层级。即，pri 管左右关系（中序）、val 管父子关系（堆），两个维度互不干扰，永远不会冲突、不会掣肘。
● 笛卡尔树（Cartesian Tree）的核心作用是把序列的区间最值问题转化为树上的 LCA（最近公共祖先）问题，从而实现 O(n) 预处理、O(1) 查询的高效解法。这得益于笛卡尔树的关键性质，即：序列区间 [L, R] 的最小值 = 笛卡尔树上结点 L 与 R 的 LCA。换句话说，笛卡尔树 = 序列的 “区间最值树形化”。笛卡尔树是算法竞赛与数据结构优化的核心工具。
● 笛卡尔树 O(n) 构建法（小根堆版）
笛卡尔树构建步骤：以序列首元素为根，遍历剩余元素逐个插入。
（1）新元素 val 更小：取代原根，将原根设为新元素的左子树。
（2）新元素 val 更大：沿根的最右路径向下查找。
找到第一个 val 比新元素大的结点 → 替换该结点，将其设为新元素的左子树。
未找到（所有最右路径结点 val 都更小）→ 直接作为最右路径最后一个结点的右子树。
（3）重复上述步骤，直至所有元素遍历完成。
● 笛卡尔树的根只由 val 决定，跟 pri 完全无关！选好根之后，直接将序列元素按下标切成两半：下标<根下标 → 全部进左子树、下标>根下标 → 全部进右子树。然后，左右子树再递归。即：左子树里再找 val 最小当左孩子、右子树里再找 val 最小当右孩子。
● 笛卡尔树构建完成后必须满足两大条件：
（1）中序遍历结果与原序列完全一致
（2）整棵树满足堆序关系
● 无论序列里有没有重复值、是否有序、是否乱序。任意一个序列，都可以唯一构造出一棵笛卡尔树。
● 基于序列 [5, 6, 3, 8, 9, 1, 4, 7, 2] 构建笛卡尔树的过程，如下所示。
● 笛卡尔树与单调栈
笛卡尔树在构建过程中，常借助“单调栈”，以保证在线性时间内完成笛卡尔树的构建。单调栈中保存的始终是笛卡尔树的右链，即由笛卡尔树的“根结点、根结点的右儿子、根结点的右儿子的右儿子、……”组成的链。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int maxn=35;
int a[maxn];
int lson[maxn],rson[maxn];
int fa[maxn];
int n;
stack<int> s;void bfs(int root) {queue<int> q;q.push(root);while(!q.empty()) {int t=q.front();q.pop();cout<<a[t]<<" ";if(lson[t]!=0) q.push(lson[t]);if(rson[t]!=0) q.push(rson[t]);}
}int main() {cin>>n;for(int i=1; i<=n; i++) {lson[i]=rson[i]=fa[i]=0;}for(int i=1; i<=n; i++) { //Cartesian Treecin>>a[i];while(!s.empty() && a[s.top()]>a[i]) {lson[i]=s.top();fa[s.top()]=i;s.pop();}if(!s.empty()) {rson[s.top()]=i;fa[i]=s.top();}s.push(i);}//Find rootint root=0;for(int i=1; i<=n; i++) {if(fa[i]==0) {root=i;break;}}bfs(root);return 0;
}/*
in:
10
8 15 3 4 1 5 12 10 18 6out:
1 3 5 8 4 6 15 10 12 18
*/
【参考文献】