检查两个树节点是否相关（即祖先后代）

• 在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）空间。

任何具有修复程序或替代方法的批评家都是可以预期的。