[Swift]LeetCode272. 最近的二分搜索树的值 II $ Closest Binary Search Tree Value II
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10678928.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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.
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
Hint:
1. Consider implement these two helper functions:
i. getPredecessor(N), which returns the next smaller node to N.
ii. getSuccessor(N), which returns the next larger node to N.
2. Try to assume that each node has a parent pointer, it makes the problem much easier.
3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
4. You would need two stacks to track the path in finding predecessor and successor node separately.
给定一个非空的二进制搜索树和一个目标值，在BST中查找离目标最近的k值。
注：
给定的目标值是一个浮点。
您可以假定k始终有效，即：k≤总节点。
保证BST中只有一组最接近目标的唯一k值。
跟进：
假设BST是平衡的，您可以在小于O（n）的运行时（其中n=总节点）中解决它吗？
提示：
1、考虑实现这两个助手函数：
i.getPrevistory（n），它将下一个较小的节点返回到n。
ii.getsuccessor（n），它将下一个较大的节点返回到n。
2、尝试假设每个节点都有一个父指针，这会使问题变得更容易。
3、如果没有父指针，我们只需要使用堆栈跟踪从根到当前节点的路径。
4、在单独查找前置节点和后续节点时，需要两个堆栈来跟踪路径。
Solution
1 public class TreeNode {
2 public var val: Int
3 public var left: TreeNode?
4 public var right: TreeNode?
5 public init(_ val: Int) {
6 self.val = val
7 self.left = nil
8 self.right = nil
9 }
10 }
11
12 class Solution {
13 func closestKValues(_ root: TreeNode?,_ target:Double,_ k:Int) -> [Int] {
14 var res:[Int] = [Int]()
15 inorder(root, target, k, &res)
16 return res
17 }
18
19 func inorder(_ root: TreeNode?,_ target:Double,_ k:Int,_ res:inout [Int])
20 {
21 if root == nil {return}
22 inorder(root?.left, target, k, &res)
23 if res.count < k
24 {
25 res.append(root!.val)
26 }
27 else if abs(Double(root!.val) - target) < abs(Double(res[0]) - target)
28 {
29 res.removeFirst()
30 res.append(root!.val)
31 }
32 else
33 {
34 return
35 }
36 inorder(root?.right, target, k, &res)
37 }
38 }