我正在编写一个 Java 方法,该方法采用二叉搜索树 (BST) T 和键 k,并返回出现在中序遍历中的第一个大于 k 的条目。如果 k 不存在或不存在大于 k 的键,则返回 null。例如,当应用于下图中的 BST 时,如果 k = 23,则应返回 29;如果 k = 32,则应返回 null。
伪代码为:
findFirstEntryLargerThanKey(BSTNode t, int key)
// go left
findFirstEntryLargerThanKey(t.left, key);
// visit the node
if t.nodeValue == key
key exists, set a boolean value to true
else if t.nodeValue > key
check if this node value is the first entry larger than key
// go right
findFirstEntryLargerThanKey(t.right, key);
到目前为止我已经编写的代码:
boolean found = false;
int x = 0;
public Integer findFirstEntryLargerThanKey(BSTNode t, int key) {
// the scan terminates on an empty subtree
if (t != null) {
// descend left
findFirstEntryLargerThanKey(t.left, key);
// visit the node
if (t.nodeValue == key){
found = true;
}
else if (t.nodeValue > key && found == true && ? && ?){
x = t.nodeValue;
}
// descend right
findFirstEntryLargerThanKey(t.right, key);
return x;
}
return null;
}
我需要有关我必须使用的条件的帮助。
最佳答案
进行中序遍历,这将按升序打印树键。同时继续比较 key 并打印第一个大于您的 key 的 key 。时间复杂度将小于 O(n)
关于java - 空白ST : return first entry larger than the key,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36324637/