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

Question

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

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

而已.我将在下面讨论我的解决方案(方法).如果你想先考虑自己,请停止.

---

对于预处理,我决定做一个预订(先递归遍历root,然后是子),并给每个节点一个标签.

让我详细解释标签.每个标签将由逗号分隔的自然数组成,如"1,2,1,4,5" - 此序列的长度等于(节点的深度+ 1).例如,根的标签是"1",root的子节点将具有标签"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)查询时间,如果存储每个顶点的预订编号和后序编号并使用此事实:

对于树T的两个给定节点x和y,x是y的祖先,当且仅当x在前序遍历中在y之前出现并且在后顺序遍历中出现在y之后.

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

你在最坏的情况下所做的是Theta(d),其中d是较高节点的深度,因此不是O(1).空间也不是O(n).