Java:如何在 BST 中找到最接近目标的 k 个值？

Question

我正在研究如何在 BST 中找到最接近目标的 k 个值，并遇到了以下使用规则的实现:

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

Given target value is a floating point.You may assume k is always valid, that is: k ≤ total nodes.You are guaranteed to have only one unique set of k values in the BST that are closest to the target. Assume that the BST is balanced.

实现的思路是:

Compare the predecessors and successors of the closest node to the target, we can use two stacks to track the predecessors and successors, then like what we do in merge sort, we compare and pick the closest one to the target and put it to the result list. As we know, inorder traversal gives us sorted predecessors, whereas reverse-inorder traversal gives us sorted successors.

代码:

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    
    TreeNode(int x) { 
        val = x; 
    }
}


public class ClosestBSTValueII {
    List<Integer> closestKValues(TreeNode root, double target, int k) {
          List<Integer> res = new ArrayList<>();

          Stack<Integer> s1 = new Stack<>(); // predecessors
          
          Stack<Integer> s2 = new Stack<>(); // successors

          inorder(root, target, false, s1);
          inorder(root, target, true, s2);
          
          while (k-- > 0) {
            if (s1.isEmpty()) {
              res.add(s2.pop());
            } else if (s2.isEmpty()) {
              res.add(s1.pop());
            } else if (Math.abs(s1.peek() - target) < Math.abs(s2.peek() - target)) {
              res.add(s1.pop());
            } else {
              res.add(s2.pop());
            }
          }
          
          return res;
        }

    // inorder traversal
    void inorder(TreeNode root, double target, boolean reverse, Stack<Integer> stack) {
      
      if (root == null) {
          return;
      }

      inorder(reverse ? root.right : root.left, target, reverse, stack);
      // early terminate, no need to traverse the whole tree
      if ((reverse && root.val <= target) || (!reverse && root.val > target)) {
          return;
      }
      // track the value of current node
      stack.push(root.val);
      inorder(reverse ? root.left : root.right, target, reverse, stack);
    }
    
    public static void main(String args[]) {
        ClosestBSTValueII cv = new ClosestBSTValueII();
        
        TreeNode root = new TreeNode(53);
        root.left = new TreeNode(30);
        root.left.left = new TreeNode(20);
        root.left.right = new TreeNode(42);
        root.right = new TreeNode(90);
        root.right.right = new TreeNode(100);
        
        System.out.println(cv.closestKValues(root, 40, 2));
    }
}

我的问题是，有两个堆栈的原因是什么？有序是一种好的方法吗？每个的目的是什么？用一个堆栈遍历它还不够吗？

reverse 有什么意义呢？ boolean 值，例如 inorder(reverse ? ...); ？在 if ((reverse && root.val <= target) || (!reverse && root.val > target)) 的情况下，你为什么提前终止？

在此先感谢您，并将接受回答/赞成票。

Answer 1

您找到的算法的思想非常简单。他们只是从target的地方按顺序遍历一棵树。应该插入。他们使用两个栈来存储前驱和后继。让我们以树为例:

     5
    / \
   3   9
  / \   \
 2   4   11 

设目标为8 .当所有inorder方法调用完成后，堆栈将是:s1 = {2, 3, 4, 5} , s2 = {11, 9} .如您所见，s1包含 target 的所有前身和 s2它的所有继承者。此外，两个堆栈都以某种方式排序，即 top每个堆栈的更接近 target ，比堆栈中的所有其他值。结果，我们很容易找到k最接近的值，只需始终比较堆栈的顶部，并弹出最接近的值，直到我们有 k值。他们算法的运行时间是O(n) .

现在谈谈你的问题。我不知道，如何使用唯一的堆栈有效地实现这个算法。堆栈的问题是我们只能访问它的顶部。但是用一个数组来实现这个算法是非常容易的。让我们按常规顺序遍历一棵树。对于我的示例，我们将得到:arr = {2, 3, 4, 5, 9, 11} .然后让我们放置l和 r两侧最接近目标值的索引:l = 3 , r = 4 ( arr[l] = 5 ， arr[r] = 9 )。剩下的就是一直比较arr[l]和 arr[r]并选择要添加到结果中的内容(绝对相同，与两个堆栈一样)。该算法还采用 O(n)操作。

他们解决问题的方法在我看来有点难以用代码理解，尽管它相当优雅。

我想介绍另一种方法来解决另一个运行时的问题。该算法将采用 O(k*logn)时间，哪个对小比较好k对于比以前的算法更大的算法更糟。

我们也存储在 TreeNode 中类指向父节点的指针。然后我们可以很容易地在 O(logn) 中找到树中任何节点的前驱或后继。时间(if you don't know how)。因此，让我们首先在树中找到目标的前驱和后继(不进行任何遍历!)。然后做与堆栈相同的事情:比较前驱\后继，选择最接近的，最接近它的前驱\后继。

我希望，我回答了您的问题并且您理解了我的解释。如果没有，请随时询问!