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

Question

我正在二叉树中做一个问题，当我遇到一个问题时，在完整二叉树的最后一层中找到最右边的节点，这里的问题是我们必须在 O(n) 时间内完成它，这是一个停止点，通过遍历所有元素，在 O(n) 中完成它很简单，但是有没有办法以小于 O(n) 的任何复杂度来完成此操作，我已经浏览了很多互联网，但我无法得到任何与该事物有关的事情。 预先感谢。

Answer 1

我假设您知道节点的数量。让

n

这样的数字。

在完全二叉树中，级别

i

的节点数是级别

i - 1

的两倍。

因此，您可以迭代地在

n

之间划分

2

。如果有余数，则

n

是右孩子；否则，是左孩子。无论是否有余数，都存储到一个序列中，最好是堆栈。

一些例如：

Stack<char> s;
while (n > 1)
{
  if (n % 2 == 0)
    s.push('L');
  else
    s.push('R');
  n = n/2; // n would int so division is floor
}

当

while

完成时，堆栈包含到最右边节点的路径。

while

执行的次数为

log_2(n)

。

Answer 2

是的，您可以在

O(log(n)^2)

中通过进行二分搜索的变体来完成此操作。

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

i

，第一个没有找到的元素是

2i

。

现在您可以简单地在该范围内进行二分搜索。

这是

O(log(n/2)) = O(logn)

总迭代次数，由于每次迭代都会沿着整棵树进行，因此总共需要

O(log(n)^2)

时间。

---

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

Answer 3

这是时间复杂度为 O(lg n* lg n) 、空间复杂度为 O(lg n) 的递归解决方案（考虑堆栈存储空间）。
使用以下代码的迭代版本可以将空间复杂度降低到 O(1)。

    // helper function
    int getLeftHeight(TreeNode * node) {
      int c = 0;
      while (node) {
        c++;
        node = node -> left;
      }
      return c;
    }
    
    int getRightMostElement(TreeNode * node) {
      int h = getLeftHeight(node);

      // base case will reach when RightMostElement which is our ans is found
      if (h == 1)
        return node -> val;

      // ans lies in rightsubtree
      else if ((h - 1) == getLeftHeight(node -> right))
        return getRightMostElement(node -> right);

      // ans lies in left subtree
      else getRightMostElement(node -> left);
    }

时间复杂度推导—— 在每个递归步骤中，我们都考虑左子树或右子树，即最大高度 (lg n) 函数调用的 n/2 个元素，
计算高度需要 lg n 时间 -

T(n) = T(n/2) + c1 lgn
   = T(n/4) + c1 lgn + c2 (lgn - 1)
   = ...
   = T(1) + c [lgn + (lgn-1) + (lgn-2) + ... + 1]
   = O(lgn*lgn)   

Answer 4

由于它是一个完整的二叉树，因此遍历所有正确的节点直到到达叶子将花费 O(logN)，而不是 O(N)。在常规二叉树中，它需要 O(N)，因为在最坏的情况下，所有节点都向右排列，但由于它是完全二叉树，所以不可能

Answer 5

这个想法是对于每个节点比较左子树和右子树的高度。通过这种方式，您可以在每一步中消除一半的节点。 复杂度为 O(log n*log n)，因为你需要 log n 步才能走下树，而获取子树的高度则需要另一个 log n。