Java BST 最有效地搜索最大值

Question

长期读者第一次发帖(主要是因为 99% 的问题已经在这里得到解答!!!)

我已经浏览了大约一个小时，但无法找到该问题的解决方案。给定一个预先排序的平衡二叉搜索树，我的任务是使用以下方法来更有效地查找树中的最大值:

private int max(IntTreeNode root) {
    if (root.left == null && root.right == null)
        return root.data;
    else {
        int maxValue = root.data;
        if (root.left != null)
            maxValue=Math.max(maxValue,max(root.left));
        if (root.right != null)
            maxValue = Math.max(maxValue,max(root.right));
        return maxValue;

这是我的两个想法(其中一个可能是错误的，这就是问题所在):

1)虽然它是排序和平衡的，但它的大小可能会有所不同，因此我必须检查每个叶子，因为该方法的唯一参数是根，我在那里看不到任何快捷方式。

2)同样的原因，单个参数，意味着我必须使用行 maxValue=Math.max(maxValue,max(root.left));在每次递归调用中，以便在 maxValue 上保留一个连续的数字。所以我不知道在哪里可以跳过这些无用的计算。

所问的问题是，在给定排序的平衡 BST 信息的情况下，如何使该方法更加高效，其他信息正是我所了解的。谢谢

编辑我想我担心的是 11 元素树

         1
       /   \
      2      3
     / \    /  \
    4  5    6    7
   / \/ \  /  \ / \  (making a tree got real hard)
  8  9 10 11        (this row is a little messed up but demonstrates the point)

重点是，如果你只走右边，你最终会得到 7，因此是错误的。除非我对排序 BST 的含义感到困惑，否则 BST 总是必须在底行填满吗？

Answer 1

在 BST 中，最右边的元素是最大值。

这是伪代码。

int getMax(Node root) { //check if root is null
   if(root.right == null) {
       return root.data 
   } else {
       return getMax(root.right)
   }
}

对于平衡树，顺序为O(log n)。