我知道如何在 O(n) 时间内将数组转换为笛卡尔树
但是，所需的内存量太高（常量），因为我需要至少将左右指针与笛卡尔树中的每个节点相关联。
任何人都可以将我与减少这些常数的工作联系起来（希望减少到 1）吗？
您不需要保持与您的笛卡尔树节点相关联的左右指针。您只需要保留每个节点的父节点并根据笛卡尔树的定义（数组 A[0, N - 1] 的笛卡尔树是二叉树 C(A)，其根是 A 的最小元素，标记为具有此最小值的位置 i。如果 i > 0，则根的左孩子是 A[0, i - 1] 的笛卡尔树，否则没有孩子。右孩子的定义与 A[i + 1 类似， N - 1].)，您可以遍历这个数组，如果节点的父节点的索引低于节点本身，则该节点将是其父节点的右子节点，同样，如果节点的父节点具有更高的索引比该节点将成为其父节点的儿子。
希望这可以帮助。
可以构造一个只有额外空间用于子到父引用（按索引）的笛卡尔树：因此，除了输入数组之外，您还需要一个大小相等的数组，其中包含与第一个数组相关的索引值。如果我们调用那个额外的数组parentOf，那么array[parentOf[i]]将是 的父级array[i]，除非array[i]是根。在那种情况下parentOf[i]应该像一个 NIL 指针（或者，例如，-1）。
关于笛卡尔树的维基百科文章，给出了一个简单的构造方法：
一种方法是在允许向上和向下遍历树的结构中以从左到右的顺序简单地处理序列值 [...]
这可能给人的印象是，该算法有必要在树中同时维护向上和向下的链接，但事实并非如此。它可以通过只维护从孩子到父母的链接来完成。
在构造过程中，将一个新值注入到以最右边节点结束的路径中（具有最近添加的值）。这条道路上的任何孩子都必然是其父母的正确孩子。
从叶子沿相反的方向走这条路时，跟踪父母及其右孩子（您来自哪里）。找到插入点后，该子节点将新节点作为父节点，新子节点将“旧”父节点作为其父节点。
在此过程中，您不需要存储指向子节点的指针。
这是用 JavaScript 编写的算法。例如，树是从输入数组 [9,3,7,1,8,12,10,20,15,18,5] 填充的。仅用于验证，输入数组和父引用都被打印：
class CartesianTree {
constructor() {
this.values = [];
this.parentOf = [];
}
extend(values) {
for (let value of values) this.push(value);
}
push(value) {
let added = this.values.length; // index of the new value
let parent = added - 1; // index of the most recently added value
let child = -1; // a NIL pointer
this.values.push(value);
while (parent >= 0 && this.values[parent] > value) {
child = parent;
parent = this.parentOf[parent]; // move up
}
// inject the new node between child and parent
this.parentOf[added] = parent;
if (child >= 0) this.parentOf[child] = added;
}
}
let tree = new CartesianTree;
tree.extend([9,3,7,1,8,12,10,20,15,18,5]);
printArray("indexes:", tree.values.keys());
printArray(" values:", tree.values);
printArray("parents:", tree.parentOf);
function printArray(label, arr) {
console.log(label, Array.from(arr, value => (""+value).padStart(3)).join(" "));
}您可以使用堆来存储树，本质上它是一个数组，其中数组中的第一个元素是根，第二个是根的左子，第三个是右，等等。它便宜得多，但需要一个编程时要多加注意。