Java：如何在BST中找到距离目标最近的k值？

Question

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

给定非空的二元搜索树和目标值，在BST中查找距离目标最近的k个值。

注：

给定的目标值是浮点。您可以假设k始终有效，即：k≤ 节点总数。保证BST中只有一组最接近目标的唯一k值。假设BST是平衡的。

实现的想法是：

比较离目标最近的节点的前辈和后辈，我们可以使用两个堆栈来跟踪前辈和后辈，然后像我们在合并排序中所做的那样，我们比较并选择离目标最近的一个并将其放入结果列表。众所周知，按顺序html" target="_blank">遍历为我们提供了排序的前辈，而按顺序反向遍历为我们提供了排序的后辈。

代码：

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

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

有一个反向布尔值的意义是什么，比如对于顺序（反向？…） ？如果<代码>if（（相反

提前向您表示感谢，并将接受回答/支持投票。

Answer 1

之所以需要两个堆栈，是因为必须在两个方向遍历树，并且必须将每个堆栈的当前值与正在搜索的值进行比较（最终可能会有k个值大于搜索值，或者k/2大于k/2，k/2小于k/2）。

我认为应该使用树节点堆栈，而不是整数堆栈；您可以避免递归。

更新时间：

我在算法中看到了两个阶段：

1）在树中找到最接近的值，这将同时构建初始堆栈。

2）复制堆栈，向后移动一个元素，这将给你第二个堆栈；然后最多迭代k次：看看每个堆栈顶部的两个元素中哪个最接近搜索到的值，将其添加到结果列表中，并向前或向后移动堆栈。

更新2：一点代码

public static List<Integer> closest(TreeNode root, int val, int k) {
    Stack<TreeNode> right = locate(root, val);
    Stack<TreeNode> left = new Stack<>();
    left.addAll(right);
    moveLeft(left);
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < k; ++i) {
        if (left.isEmpty()) {
            if (right.isEmpty()) {
                break;
            }
            result.add(right.peek().val);
            moveRight(right);
        } else if (right.isEmpty()) {
            result.add(left.peek().val);
            moveLeft(left);
        } else {
            int lval = left.peek().val;
            int rval = right.peek().val;
            if (Math.abs(val-lval) < Math.abs(val-rval)) {
                result.add(lval);
                moveLeft(left);
            } else {
                result.add(rval);
                moveRight(right);
            }
        }
    }
    return result;
}

private static Stack<TreeNode> locate(TreeNode p, int val) {
    Stack<TreeNode> stack = new Stack<>();
    while (p != null) {
        stack.push(p);
        if (val < p.val) {
            p = p.left;
        } else {
            p = p.right;
        }
    }
    return stack;
}

private static void moveLeft(Stack<TreeNode> stack) {
    if (!stack.isEmpty()) {
        TreeNode p = stack.peek().left;
        if (p != null) {
            do {
                stack.push(p);
                p = p.right;
            } while (p != null);
        } else {
            do {
                p = stack.pop();
            } while (!stack.isEmpty() && stack.peek().left == p);
        }
    }
}

private static void moveRight(Stack<TreeNode> stack) {
    if (!stack.isEmpty()) {
        TreeNode p = stack.peek().right;
        if (p != null) {
            do {
                stack.push(p);
                p = p.left;
            } while (p != null);
        } else {
            do {
                p = stack.pop();
            } while (!stack.isEmpty() && stack.peek().right == p);
        }
    }
}

更新3

用一个堆栈遍历它还不够吗？

有一个反向布尔值的意义是什么，比如对于inorder（反向？…）；？如果是if（（相反

我不知道你从哪里得到你在问题中给出的解决方案，但是总结一下，它构建了两个整数列表，一个按直线顺序，一个按倒序。当达到搜索值时，它会“提前”终止。这个解决方案听起来效率很低，因为它需要遍历整个树。当然，我的要好得多，而且它符合给定的规则。

Answer 2

您找到的算法的思想非常简单。它们只是从应该插入目标的位置按顺序遍历树。它们使用两个堆栈来存储前置和后续。以树为例：

     5
    / \
   3   9
  / \   \
 2   4   11 

让目标为8。当所有按序调用完成时，堆栈将是：s1={2，3，4，5}，s2={11，9}。如您所见，s1包含目标的所有前辈，以及它的所有后继者。此外，两个堆栈的排序方式是，每个堆栈的顶部比堆栈中的所有其他值更接近目标值。因此，我们可以很容易地找到最接近的值，只需始终比较堆栈的顶部，并弹出最接近的值，直到我们有了值。他们算法的运行时间是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）时间内（如果您不知道怎么做的话）轻松地找到树中任何节点的前置节点或后续节点。因此，让我们首先在树中找到目标的前一个和后一个（无需进行任何遍历！）。然后执行与堆栈相同的操作：比较前置器\后续器，选择最近的一个，对于最近的，转到其前置器\后续器。

我希望，我回答了你的问题，你理解我的解释。如果没有，请随时提问！