algorithm - 通过预处理检查 O(1) 中的 2 个树节点是否相关(祖先/后代)

Question

检查 2 个树节点是否相关(即祖先-后代)

• 用 O(N) 空间(N = 节点数)在 O(1) 时间内解决它
• 允许预处理

就是这样。我将在下面介绍我的解决方案(方法)。如果您想先考虑自己，请停下来。

---

对于预处理，我决定进行预排序(先递归地遍历根节点，然后是子节点)并为每个节点指定一个标签。

让我详细解释一下标签。每个标签将由以逗号分隔的自然数组成，例如“1,2,1,4,5”——该序列的长度等于(节点的深度 + 1)。例如。根的标签是“1”，根的子节点将有标签“1,1”、“1,2”、“1,3”等。下一级节点将有标签如“1,1,1” , "1,1,2", ..., "1,2,1", "1,2,2", ...

假设一个节点的“序号”是其父节点的子列表中的“该节点的从1开始的索引”。

通用规则:节点的标签由其父标签后跟逗号和节点的“序号”组成。

因此，为了回答两个节点是否在 O(1) 中相关(即祖先-后代)，我将检查其中一个节点的标签是否是节点的“前缀”别人的标签。虽然我不确定这样的标签是否可以被认为占用 O(N) 空间。

任何有修复或替代方法的批评都在意料之中。

Answer 1

如果您存储每个顶点的前序号和后序号并使用以下事实，您可以在 O(n) 的预处理时间和 O(n) 的空间以及 O(1) 的查询时间中完成此操作:

For two given nodes x and y of a tree T, x is an ancestor of y if and only if x occurs before y in the preorder traversal of T and after y in the post-order traversal.

(来自本页:http://www.cs.arizona.edu/xiss/numbering.htm)

在最坏的情况下，您所做的是 Theta(d)，其中 d 是更高节点的深度，因此不是 O(1)。空间也不是 O(n)。