想象一下下面的树：
A
/ \
B C
/ \ \
D E F
我正在寻找一种方法来查询 F 是否是 A 的后代（注意：F 不需要是directA) 的后代，在这种特殊情况下这是正确的。只需要针对更大的潜在后代节点池测试有限数量的潜在父节点。
当测试一个节点是否是潜在父池中节点的后代时，需要针对所有潜在父节点进行测试。
这是a想出的：
-
将多路树转换为 trie，即为上述树中的每个节点分配以下前缀：
A = 1
B = 11
C = 12
D = 111
E = 112
F = 121
-
然后，为每个可能的前缀大小保留一个位数组，并添加要测试的父节点，即，如果将 C 添加到潜在父节点池，请执行以下操作：
1 2 3 <- Prefix length
*[1] [1] ...
[2] *[2] ...
[3] [3] ...
[4] [4] ...
... ...
-
当测试一个节点是否是潜在父节点的后代时，获取其 trie 前缀，查找第一个“前缀数组”中的第一个字符（见上文），如果存在，则查找第二个“前缀数组”中的第二个前缀字符array”等等，即测试 F 会导致：
F = 1 2 1
*[1] [1] ...
[2] *[2] ...
[3] [3] ...
[4] [4] ...
... ...
所以是的，F是C的后代。
这个测试似乎是最坏情况 O(n)，其中 n = 最大前缀长度 = 最大树深度，所以它的最坏情况完全等于直接上树并比较节点的明显方法。但是，如果测试的节点位于树的底部附近并且潜在的父节点位于顶部的某个位置，则效果会更好。结合这两种算法将缓解两种最坏的情况。然而，内存开销是一个问题。
还有其他方法可以做到这一点吗？任何指点都非常感谢！
你的输入树总是静态的吗？如果是这样，那么您可以使用最低公共祖先算法通过 O(n) 时间/空间构造在 O(1) 时间内回答是否是后代问题。 LCA 查询给定两个节点，并询问哪个是子树包含这两个节点的树中最低的节点。然后，您可以使用单个 LCA 查询来回答 IsDescentent 查询，如果 LCA(A, B) == A 或 LCA(A, B) == B，则一个是另一个的后代。
This 对问题进行了彻底的讨论，并提供了不同级别的代码复杂性/效率的一些解决方案。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
