BST中的最近密钥前（k）

Question

我试图在二叉搜索树中达到k之前找到最接近k的密钥。 我越想越想弄清楚它可能在哪里。

这种方法的正式定义： 返回该项目的核心与关键最大小于或等于k

起初，我认为这将是k的父母..但看着BSTS后的对我来说变得很不清楚。我需要这个算法。 它应该在O（h）时间运行，其中h是树的高度。

谢谢！

Answer 1

我想你可以利用递归来记住你当前的最佳值（即迄今为止最接近的值）。如果值大于当前节点，则搜索右侧子树，并且如果在右侧子树中找不到任何内容，则知道当前节点是最佳答案。在搜索正确的子树时，你返回你当前的最佳答案（小于或等于），这个答案只会传播开来。

当值小于当前节点时，搜索左侧子树。当前节点不能成为您的最佳答案，因为它大于您正在搜索的值。因此，只需返回任何左子树返回。

代码看起来像这样。这只是整数的一个简单示例，当没有找到有效值时它返回-1。

public static int closestKeyBefore(Node node, int val) { 
    if(node==null) return -1; 

    if(node.value == val) return val; 

    int retval = -1; 
    if(node.value<val) { // Value is bigger than current node, search right 
     retval = closestKeyBefore(node.right,val); 
     if(retval==-1) { //Not found in right subtree 
      retval = node.value; // Current node is the best answer. return this 
     } 
    } 
    else { // Value is smaller than current node, search left 
     retval = closestKeyBefore(node.left,val); 
    } 
    return retval; 
}