algorithm - 如何在完全二叉树的最后一层中找到最右边的节点的位置？

Question

我在做一个二叉树的问题，当我遇到一个问题时，在完整的二叉树的最后一层找到最右边的节点，这里的问题是我们必须在 O(n) 时间内完成它是一个停止点，通过遍历所有元素在 O(n) 中完成它很简单，但是有没有办法以低于 O(n) 的复杂性来做到这一点，我浏览了很多互联网，但我不能'对这件事一无所知。提前致谢。

Answer 1

是的，您可以通过二进制搜索的变体在 O(log(n)^2) 中完成。

这可以通过首先转到最左边的元素¹ 来完成，然后是第二个最左边的元素，然后是第四个最左边的元素，第 8 个，...直到你发现没有这样的元素.假设您找到的最后一个元素是第 i 个，而第一个没有找到的元素是 2i。

现在您可以简单地对该范围进行二分查找。

这是 O(log(n/2)) = O(logn) 总迭代次数，并且由于每次迭代都是沿着整棵树向下进行，所以它的总次数为 O(log( n)^2) 时间。

---

(1) 此处及下文中，“x最左元素”仅指树中最深层次的节点。