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

我研究如何找到在BST是最接近目标的k值，和整个以下实现的规则来：Java：如何在BST中找到最接近目标的k值？

给定一个非空的二叉搜索树和目标值，在BST中找到最接近目标的k值。

注意：

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

而实施的思路是：

比较的前辈和最近的节点的接班人为目标，我们可以用两个堆栈跟踪前辈和接班人，然后像我们做什么在合并排序中，我们比较并选取距目标最近的一个并将其放到结果列表中。我们知道，遍历给了我们排序的前辈，而逆向遍历给了我们排序的后继者。

代码：

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布尔值，比如inorder(reverse ? ...);？而在if ((reverse && root.val <= target) || (!reverse && root.val > target))的情况下，为什么你提前终止？

谢谢你在前进，并会接受的答案/上投票。

来源

2016-12-12 Jo Ko

如果你的代码已经有效，那么这个问题可能更适合于[Code Review]（http://codereview.stackexchange.com）网站。 –

不知道我理解你的问题，你想找到后继节点吗？你可以用递归方法做到这一点。 – Baxtex

@Baxtex我只是想了解这种方法。 –

你需要两个堆栈的原因是你必须在两个方向上遍历树，并且你必须将每个堆栈的当前值与你正在搜索的值进行比较（你可能最终的k值大于搜索值，或k/2更大和k/2更低）。

我认为你应该使用堆叠的TreeNodes，而不是堆叠的整数;你可以避免递归。

UPDATE：

我看到在算法两个阶段：

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（反向？...）;？而在情况下，如果（（反& & root.val < =目标）||（！反向& & root.val>目标）），你为什么要终止早？

我不知道你从哪里得到的解决方案是你提出的问题，但总而言之，它构建了两个整数列表，一个按顺序排列，一个按相反顺序排列。当搜索到的值达到时它终止“提前”。这个解决方案听起来非常低效，因为它需要遍历整个树。我的矿井当然好得多，它符合给定的规则。

来源

2016-12-12 09:36:24

您发现算法的想法很简单。他们只是从该地方按顺序遍历一棵树，在那里应该插入target。他们使用两个堆栈来存储前辈和后继者。让我们以树为例：

让目标为8。当所有inorder方法调用完成后，堆栈将为：s1 = {2, 3, 4, 5},s2 = {11, 9}。正如你看到的，s1包含所有的前辈target和s2它的所有继承者。此外，两个堆栈都按照某种方式排序，即每个堆栈的top比堆栈中的所有其他值更接近target。因此，我们可以很容易地找到最接近的值，只需始终比较堆栈的顶部，然后弹出最接近的值，直到获得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）找到树中任何节点的前任或继任者。因此，我们首先在目标树的前辈和后继者中找到它（不进行任何遍历！）。然后执行与堆栈相同的操作：比较predecessor \ successor，选择最接近的一个，并选择最接近它的前辈\后继者。

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

来源

2016-12-12 11:14:54

如果你不能，或者不想添加一个父指针，你可以使用两个堆栈。 –

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

回答

相关问题