在完美二叉树中寻找共同 parent
Finding common parent in perfect binary tree
本题：
提供了一种标记任意深度的完美二叉树的分析方法。
在这样的树中，是否有任何方法可以有效地找出叶节点的任意子集的第一个公共 parent？
例如，给定以下二叉树：
我正在寻找一种方法，如果：
输入是：3,5输出是：0
输入是：3,5,6输出是：0
输入是：3,4输出是：1
我能想到的唯一方法是从每个给定的叶节点向上遍历到根（0），然后选择第一个公共的。
有没有什么closed-form分析方法可以找到第一个常见的parent？
让 H 成为你的树的高度，让 k 成为你输入的数字的数量。
如果节点从1开始计数，写节点的二进制数，就会明白每个节点的数字都是其所有子节点数字的前缀。所以，要找到最低公共祖先，你应该找到二进制数的最大公共前缀（GCP）。
设 min 和 max 是您子集中的最小和最大数字。如果您输入的数字已经排序，您可以在 O(1) 中找到 min 和 max。如果没有排序，可以在O(k * H).
中找到min和max
所有二进制数的 GCP 是 min 和 max 的 GCP - 您可以在 O(H).
中轻松找到它
如果数字已排序，此算法在 O(H) 中有效，否则在 O(k * H) 中有效（尽管如果正确实施，您的算法在 O(k * H) 中也有效）。
本题：
提供了一种标记任意深度的完美二叉树的分析方法。
在这样的树中，是否有任何方法可以有效地找出叶节点的任意子集的第一个公共 parent？
例如，给定以下二叉树：
我正在寻找一种方法，如果：
输入是：3,5输出是：0
输入是：3,5,6输出是：0
输入是：3,4输出是：1
我能想到的唯一方法是从每个给定的叶节点向上遍历到根（0），然后选择第一个公共的。
有没有什么closed-form分析方法可以找到第一个常见的parent？
让 H 成为你的树的高度，让 k 成为你输入的数字的数量。
如果节点从1开始计数，写节点的二进制数，就会明白每个节点的数字都是其所有子节点数字的前缀。所以，要找到最低公共祖先，你应该找到二进制数的最大公共前缀（GCP）。
设 min 和 max 是您子集中的最小和最大数字。如果您输入的数字已经排序，您可以在 O(1) 中找到 min 和 max。如果没有排序，可以在O(k * H).
min和max
所有二进制数的 GCP 是 min 和 max 的 GCP - 您可以在 O(H).
如果数字已排序，此算法在 O(H) 中有效，否则在 O(k * H) 中有效（尽管如果正确实施，您的算法在 O(k * H) 中也有效）。