Java BST 最有效地搜索最大值
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20544336/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java BST searching for max value, most efficiently
提问by Danny Randolph
Long time reader first time poster (mostly because 99% of all questions have already been answered on here!!!)
长期读者第一次发帖（主要是因为这里已经回答了 99% 的问题！！！）
I've been browsing for about an hour and I am unable to find a solution to this problem. Given a pre-sorted balanced binary search tree, I am tasked with making the following method to find the max value in the tree more efficient:
我已经浏览了大约一个小时，但找不到解决此问题的方法。给定一个预先排序的平衡二叉搜索树，我的任务是使以下方法更有效地找到树中的最大值：
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;
Here are my 2 thoughts (and likely one of them is wrong and that's the problem):
这是我的 2 个想法（其中一个可能是错误的，这就是问题所在）：
1) While it is sorted and balanced, it can vary in size, therefore I have to check each and every leaf, because the only parameter to the method is a root I don't see any shortcut there.
1）虽然它是排序和平衡的，但它的大小可能会有所不同，因此我必须检查每一片叶子，因为该方法的唯一参数是根，我在那里看不到任何快捷方式。
2) Same cause, single parameter, means I have to use the line maxValue=Math.max(maxValue,max(root.left)); in each recursive call in order to keep a running number on maxValue. So I don't see where to skip any of those useless calculations.
2）相同的原因，单个参数，意味着我必须使用行 maxValue=Math.max(maxValue,max(root.left)); 在每次递归调用中，以便在 maxValue 上保持一个运行数字。所以我看不出哪里可以跳过这些无用的计算。
The question being asked, is how would you make the method more efficient given the sorted balanced BST information, the other information is just where I am on it all. Thanks
被问到的问题是，在给定排序的平衡 BST 信息的情况下，您如何使该方法更有效，而其他信息正是我所掌握的。谢谢
editI guess I was worried about an 11 element tree
编辑我想我担心的是 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)
Point being if you only take the right, you will end up at 7, and thus be wrong. Unless I'm confused on the meaning of sorted BST, do BST's always have to be full on the bottom row?
重点是，如果你只选择正确的，你最终会得到 7 点，因此是错误的。除非我对排序 BST 的含义感到困惑，否则 BST 是否总是必须在底行填满？
采纳答案by 4J41
In a BST the right most element is the maximum.
在 BST 中，最右边的元素是最大值。
Here is the pseudocode.
这是伪代码。
int getMax(Node root) { //check if root is null
if(root.right == null) {
return root.data
} else {
return getMax(root.right)
}
}
For a balanced tree, order would be O(log n).
对于平衡树，顺序是O(log n)。
回答by Khalid Abu El-Soud
for the LHS it always less than the root so no need to search for you can use this one :
对于 LHS，它总是小于根，因此无需搜索即可使用此：
private int max(IntTreeNode root) {
if ( root.right == null) // no need to search in LHS
return root.data;
else {
int maxValue = root.data;
maxValue = Math.max(maxValue,max(root.right));
}
return maxValue;
if this is not you want asked me again what are you want is your expected output from this method and I'll try to help you :)
如果这不是你想再次问我你想要什么是这个方法的预期输出，我会尽力帮助你:)
