algorithm - 有效地将数组转换为笛卡尔树

Question

我知道如何在 O(n) 时间内将数组转换为笛卡尔树

1. http://en.wikipedia.org/wiki/Cartesian_tree#Efficient_construction和
2. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#From RMQ 到 LCA

但是，所需的内存量太高(常量)，因为我需要至少将左指针和右指针与笛卡尔树中的每个节点相关联。

任何人都可以将我与减少这些常量(希望减少到 1)所做的工作联系起来吗？

Answer 1

您不需要保持与笛卡尔树节点关联的左右指针。您只需要保留每个节点的父节点并根据笛卡尔树的定义(数组 A[0, N - 1] 的笛卡尔树是二叉树 C(A)，其根是 A 的最小元素，标有此最小值的位置 i。根的左子节点是笛卡尔A[0, i - 1] 的树，如果 i > 0，否则没有 child 。右 child 的定义类似于 A[i + 1, N - 1]。)，你可以遍历这个数组，如果节点的父节点的索引低于节点本身，因此节点将成为其父节点的右儿子，类似地，如果节点的父节点具有比节点更高的索引，则节点将成为其父节点的左儿子。

希望这对您有所帮助。