# [Swift]LeetCode272. 最近的二分搜索树的值 II \$ Closest Binary Search Tree Value II

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/

➤GitHub地址：https://github.com/strengthen/LeetCode

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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, 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.

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 }```