您如何以O（log n）乘以复杂度来计算平衡二叉搜索树的高度？

Question

我知道，为了计算O（n）中的二叉搜索树的高度，我们可以使用以下函数

public static int Height(Node root) {
      if (root == null) {
         return -1;
      }

      int left = Height(root.left) + 1;
      int right = Height(root.right) + 1;

      return Math.max(left, right);
   }  

但是，鉴于树为balanced的事实，我们如何在O（log n）中计算二叉搜索树的高度。

给定的问题：

Answer 1

不可能。

如果最下面一行以可预测的方式填写，则可以完成。例如，如果最后一行总是从左到右填充，则可以在O（log n）的时间内向左下降，因为可以保证左侧具有最大高度。

在问题陈述中，底行中的节点可以在任何地方。无法以O（log n）的时间计算确切的高度。您可以在O（log n）步中获得高度的1个以内，但是要获取确切的高度，您可能必须检查树底部的n / 2个节点以找到散乱者（如果有）。

最坏的情况是，如果最后一个级别完全满了，并且必须检查最后一个级别中的每个节点是否有子代。将有n / 2个节点，每个节点有两个检查，因此总共n个检查。在这种情况下不会有任何孩子，但是仍然需要O（n）检查来验证它。