检查2个树节点是否相关（即祖先-后代）
而已。我将在下面介绍我的解决方案（方法）。如果您想先考虑自己，请停下来。
对于预处理，我决定进行预排序（首先递归地遍历根，然后是子节点）并为每个节点提供一个标签。
让我详细解释一下标签。每个标签将由逗号分隔的自然数组成，例如 "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) 空间。
预计会有任何有修复或替代方法的批评者。
您可以在 O(n) 预处理时间和 O(n) 空间中执行此操作，查询时间为 O(1)，如果您存储每个顶点的前序号和后序号并使用以下事实：
对于树 T 的两个给定节点 x 和 y，x 是 y 的祖先当且仅当 x 在 T 的前序遍历中出现在 y 之前，在后序遍历中出现在 y 之后。
（从此页面：http ://www.cs.arizona.edu/xiss/numbering.htm ）
您在最坏的情况下所做的是 Theta(d)，其中 d 是较高节点的深度，因此不是 O(1)。空间也不是 O(n)。
如果您考虑一棵树，其中树中的一个节点有 n/2 个子节点（例如），则设置标签的运行时间将高达 O(n*n)。所以这个标签方案行不通....
有线性时间最低的共同祖先算法（至少离线）。例如看看这里。你也可以看看tarjan 的离线 LCA 算法。请注意，这些文章要求您提前知道要执行 LCA 的配对。我认为也有在线线性时间预计算时间算法，但它们非常复杂。例如，对于范围最小查询问题，有一个线性预计算时间算法。据我记得这个解决方案两次通过了 LCA 问题。该算法的问题在于它具有如此大的常数，以至于它需要大量输入才能实际上比 O(n*log(n)) 算法更快。
有更简单的方法需要 O(n*log(n)) 额外的内存并在恒定时间内再次回答。
希望这可以帮助。