java - 空白ST : return first entry larger than the key

Question

我正在编写一个 Java 方法，该方法采用二叉搜索树 (BST) T 和键 k，并返回出现在中序遍历中的第一个大于 k 的条目。如果 k 不存在或不存在大于 k 的键，则返回 null。例如，当应用于下图中的 BST 时，如果 k = 23，则应返回 29；如果 k = 32，则应返回 null。

/image/ydiBv.jpg

伪代码为:

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;
}

我需要有关我必须使用的条件的帮助。

Answer 1

进行中序遍历，这将按升序打印树键。同时继续比较 key 并打印第一个大于您的 key 的 key 。时间复杂度将小于 O(n)