我在做一个二叉树的问题,当我遇到一个问题时,在完整的二叉树的最后一层找到最右边的节点,这里的问题是我们必须在 O(n) 时间内完成它是一个停止点,通过遍历所有元素在 O(n) 中完成它很简单,但是有没有办法以低于 O(n) 的复杂性来做到这一点,我浏览了很多互联网,但我不能'对这件事一无所知。 提前致谢。
最佳答案
是的,您可以通过二进制搜索的变体在 O(log(n)^2)
中完成。
这可以通过首先转到最左边的元素1 来完成,然后是第二个最左边的元素,然后是第四个最左边的元素,第 8 个,...直到你发现没有这样的元素.
假设您找到的最后一个元素是第 i
个,而第一个没有找到的元素是 2i
。
现在您可以简单地对该范围进行二分查找。
这是 O(log(n/2)) = O(logn)
总迭代次数,并且由于每次迭代都是沿着整棵树向下进行,所以它的总次数为 O(log( n)^2)
时间。
(1) 此处及下文中,“x最左元素”仅指树中最深层次的节点。
关于algorithm - 如何在完全二叉树的最后一层中找到最右边的节点的位置?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38264609/