algorithm - 在完美二叉树中找到共同父节点

Question

这个问题：

是否有任何有效的方法来填充平衡的树结构

提供了一种标记任意深度的完美二叉树的分析方法。

在这样的树中，有没有办法有效地找出任意叶节点子集的第一个公共父节点？

例如，给定以下二叉树：

我正在寻找一种方法，如果：

输入是：3,5输出是：0

输入是：3,5,6输出是：0

输入是：3,4输出是：1

我能想到的唯一方法是从每个给定的叶节点遍历到根 (0)，然后选择第一个公共叶节点。

有没有可以找到第一个共同父母的封闭式分析方法？

标签： algorithmbinary-tree

Answer 1

让H你的树的高度，让k你的输入中的数字计数。

如果从 1 开始计算节点并写入节点的二进制数，则很明显每个节点的编号都是其所有子节点编号的前缀。因此，要找到最低的共同祖先，您应该找到二进制数的最大公共前缀 (GCP)。

让minandmax成为您的子集中的最小和最大数字。min如果您输入的数字已经排序，您可以max在O(1). 如果它们没有排序，您可以在中找到min和。maxO(k * H)

所有二进制数的 GCP 是min和的 GCP max- 你可以在O(H).

O(H)如果数字已排序，则此算法适用，O(k * H)否则（尽管O(k * H)如果您正确实施，您的算法也适用）。