java - Java BST最有效地搜索最大值

长期的读者第一次海报（主要是因为这里已经回答了所有问题的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是否总是必须在最下面一行填满？

最佳答案

在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)。