笛卡尔树 (Cartesian Tree)

什么是笛卡尔树？

笛卡尔树（Cartesian Tree）是一种二叉树，由一个唯一的数值序列构建而成，它同时具有以下性质（以小根堆为例）：

二叉搜索树性质（BST）：节点在树中的中序遍历结果，与原序列的索引顺序完全一致。也就是说，左子树的索引比根节点小，右子树的索引比根节点大。
堆性质（Heap）：父节点的值总是小于或等于任何一个子节点的值。

单调栈 $O(N)$ 建树步骤

我们使用一个单调递增栈来存储当前树中从根节点一直往右伸展的右斜链节点（索引与数值均单调递增）：

当新元素 $i$ 入树时，我们从单调栈中不断弹出大于 $arr[i]$ 的元素，直到栈顶元素小于 $arr[i]$。
这批被弹出的元素中，最后一个被弹出的节点（说明是弹出元素里最大的，也是离 $i$ 索引最近的）成为新元素 $i$ 的左孩子。
如果单调栈不为空，则栈顶的元素（数值小于 $arr[i]$）成为新元素 $i$ 的父节点（即 $i$ 成为栈顶元素的右孩子）。
将新元素 $i$ 压入单调栈中。

点击"单步建树"或"自动建树"来开始追踪 $O(N)$ 单调栈构建小根堆笛卡尔树的精彩逻辑。

输入序列 A

构建形态（小根堆，左孩子 < 根 < 右孩子）

单调递增栈 (递增)

栈顶 (Top)

C++ 核心代码对照

单调栈 $O(N)$ 构建笛卡尔树 C++ 标准实现

struct CSNode {
    int val, id;
    int left, right; // 左右孩子索引
} tree[MAXN];

void buildCartesianTree(int n, const vector<int>& a) {
    stack<int> stk; // 存储数组索引的单调递增栈
    
    for (int i = 0; i < n; i++) {
        tree[i].val = a[i];
        tree[i].id = i;
        tree[i].left = tree[i].right = -1; // 初始无孩子

        int lastPopped = -1;
        // 从栈中弹出所有大于当前值的元素
        while (!stk.empty() && tree[stk.top()].val > a[i]) {
            lastPopped = stk.top();
            stk.pop();
        }

        // 1. 最后一个弹出的节点成为当前节点的左孩子
        if (lastPopped != -1) {
            tree[i].left = lastPopped;
        }

        // 2. 当前节点成为此时栈顶的右孩子
        if (!stk.empty()) {
            tree[stk.top()].right = i;
        }

        stk.push(i); // 当前节点入栈
    }
}