# 二叉树遍历：笛卡尔树

Codex（GPT-6）将先序排名转化为本题的笛卡尔树优先级，并应用已有的单调栈建树方法。程序：[alternative-cartesian.cpp](alternative-cartesian.cpp)。区间划分方案见[主解](solution.zh.md)。

## 转换为笛卡尔树

令 $\operatorname{rank}(u)$ 为编号 $u$ 在先序中的位置。按照中序排列结点，取先序排名为优先级。原二叉树满足：中序次序固定，且每个父结点的排名小于孩子的排名，因为先序总在子树前访问根。

因此它正是这个优先级序列的最小笛卡尔树。优先级互异，区间最小值唯一确定根，递归确定左右子树，所以满足这两项性质的树唯一。

## 单调栈构造

从左到右扫描中序位置。栈保存已建部分的右侧链，排名从栈底到栈顶严格递增。处理新结点时，弹出所有排名比它大的栈顶，记录最后弹出的结点作为新结点的左孩子；如果栈还非空，把新结点设为栈顶的右孩子，最后压入新结点。

弹出的右侧链整体位于新位置的左边，又都有更大优先级，所以成为新结点的左子树。未弹出的栈顶优先级更小，可作为其父结点。每步保持中序次序和最小堆性质，因此最终得到唯一的目标树。

## 后序与复杂度

使用显式栈按根、右、左顺序访问结点，把记录逆序即得左、右、根的后序。不要把通常的根、左、右访问直接逆序，否则左右次序会颠倒。

每个结点在建树单调栈中入栈、出栈各至多一次，遍历也访问一次，总时间 $O(n)$ ，空间 $O(n)$ .需要排名表、中序数组、孩子数组和遍历记录。它的价值是不同的建模及显式树结构，不宣称比区间划分更快或内存更少。实际测量见[主解](solution.zh.md#验证与运行)。