LeetCode 272. 最接近的二叉搜索树值 II
题目描述
题意分析
从二叉搜索树中选出与
target绝对差最小的k个节点值。目标可以在树值范围之内或之外，返回最近的值集合即可，不要求结果按距离或数值排序。本篇两种实现按
1 <= k <= 树的节点数处理，不修改树的连接。第一种完整取得有序值后筛选；第二种按需取得前驱、后继，避免提前保存整棵树。代码在等距时优先保留较小值。
解法一：中序展开后排除较远端
核心思路
[!blue]
二叉搜索树的中序访问顺序就是节点值的升序顺序。先用显式栈完成左、根、右遍历，将问题转为有序数组中选出最近的
k项。当前有序区间中的值都夹在两端之间。无论目标在区间内部还是外部，到目标的最大距离总能在某一端取得，所以比较端点的绝对差就能找到一个最不需要保留的值。
每次排除较远端，相当于删除当前候选中的最差项，不会漏掉所需的最近值。等距时删右端，按本实现约定保留较小值；不断收缩直到区间长度为
k。两个指针只描述保留范围，不真正删除列表元素，避免反复搬移。最后复制这个连续区间作为答案，中序遍历和端点排除都只做线性次数的处理。
解题步骤
- 用显式栈中序遍历，生成升序节点值列表。
- 左右指针分别指向列表两端。
- 区间长度大于
k时比较两端距离，移动较远端；等距时右端左移。- 剩下恰好
k项时，复制闭区间[left, right]返回。
代码实现
class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> values = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
values.add(root.val);
root = root.right;
}
int left = 0;
int right = values.size() - 1;
while (right - left + 1 > k) {
if (Math.abs(values.get(left) - target) > Math.abs(values.get(right) - target)) {
left++;
} else {
right--;
}
}
return new ArrayList<>(values.subList(left, right + 1));
}
}
import "math"
func closestKValues(root *TreeNode, target float64, k int) []int {
values := []int{}
stack := []*TreeNode{}
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
values = append(values, root.Val)
root = root.Right
}
left, right := 0, len(values)-1
for right-left+1 > k {
if math.Abs(float64(values[left])-target) > math.Abs(float64(values[right])-target) {
left++
} else {
right--
}
}
return append([]int(nil), values[left:right+1]...)
}
复杂度分析
- 时间复杂度：$O(n)$，完整遍历后至多排除
n - k项，再复制k项。- 空间复杂度：辅助空间 $O(n)$，保存有序列表与遍历栈；结果另占 $O(k)$。
关键点总结
[!green]
- BST 中序直接提供有序值，最远候选必在区间端点之一。
- 每次删一个最差项，直到保留数量达到
k。- 指针移动代替实际删除，避免在列表内部逐次搬移。
解法二：前驱栈与后继栈按需取值
核心思路
[!blue]
不展开全部值时，可以从目标两侧向外取。
lower从大到小提供不大于目标的前驱，upper从小到大提供大于目标的后继；两条序列各自与目标的距离都只会增大。比较两边当前最近项并取较近者，就相当于归并两个按距离有序的候选流。初始化只沿一条 BST 搜索路径下降。当前值不大于目标时压入前驱栈，再向右寻找更大的合格值；大于目标时压入后继栈，再向左寻找更小的合格值。到空节点时，两栈顶就是各自一侧最近的候选，栈中祖先则保留了继续遍历的入口。
取出前驱后，下一个更小值可能来自它的左子树。进入左子树并沿右链压栈，就把其中最大的剩余值放到栈顶；若左子树为空，已有栈顶祖先自然成为下一前驱。取后继时对称地进入右子树，再沿左链压栈。
两侧分别覆盖
<= target与> target，因此同一节点不会被重复取出。某侧为空时只选另一侧；两侧都有时比较栈顶距离，等距优先取前驱。每次只推进被选中的那一侧。栈顶已经是本侧最接近的未选项，未展开的其余值不会更近，所以这一轮选出的也是所有剩余节点中的最近值。重复
k次即可；每个展开节点只压栈一次，无需遍历远处不参与答案的子树。
解题步骤
- 沿搜索路径初始化两栈，按是否不大于目标划到互斥的两侧。
- 选择非空侧，或在两侧非空时比较两个栈顶的距离。
- 弹出前驱后补入其左子树的右链；弹出后继后补入其右子树的左链。
- 收集
k个值后返回，输出无须重新排序。
代码实现
class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
Deque<TreeNode> lower = new ArrayDeque<>();
Deque<TreeNode> upper = new ArrayDeque<>();
while (root != null) {
if (root.val <= target) {
lower.push(root);
root = root.right;
} else {
upper.push(root);
root = root.left;
}
}
List<Integer> answer = new ArrayList<>();
while (answer.size() < k) {
if (upper.isEmpty()
|| !lower.isEmpty() && target - lower.peek().val <= upper.peek().val - target) {
TreeNode node = lower.pop();
answer.add(node.val);
node = node.left;
while (node != null) {
lower.push(node);
node = node.right;
}
} else {
TreeNode node = upper.pop();
answer.add(node.val);
node = node.right;
while (node != null) {
upper.push(node);
node = node.left;
}
}
}
return answer;
}
}
func closestKValues(root *TreeNode, target float64, k int) []int {
lower, upper := []*TreeNode{}, []*TreeNode{}
for root != nil {
if float64(root.Val) <= target {
lower = append(lower, root)
root = root.Right
} else {
upper = append(upper, root)
root = root.Left
}
}
answer := make([]int, 0, k)
for len(answer) < k {
if len(upper) == 0 || len(lower) > 0 && target-float64(lower[len(lower)-1].Val) <= float64(upper[len(upper)-1].Val)-target {
node := lower[len(lower)-1]
lower = lower[:len(lower)-1]
answer = append(answer, node.Val)
node = node.Left
for node != nil {
lower = append(lower, node)
node = node.Right
}
} else {
node := upper[len(upper)-1]
upper = upper[:len(upper)-1]
answer = append(answer, node.Val)
node = node.Right
for node != nil {
upper = append(upper, node)
node = node.Left
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(h + k)$，
h为树高。初始化最多下降一条根路径；之后取出k项，每个展开节点只压栈一次，仍待取出的栈内候选合计为 $O(h)$。- 空间复杂度：两栈辅助空间 $O(h)$，输出占 $O(k)$。平衡树的高度为 $O(\log n)$，退化树可能为 $O(n)$。
关键点总结
[!green]
- 前驱值递减、后继值递增，两侧到目标的距离却都递增，因此可以归并取最近项。
- 每次只推进已取值一侧，另一侧的当前候选仍是本侧最近值。
- 完整展开法直接但必遍历整树，双栈法的处理量与树高和输出数量有关。
O(h + k)不能无条件写成O(log n + k)，还需考虑树的高度。
易错点总结
[!yellow]
- 前驱与后继的范围必须互斥，等于目标的节点不能同时登记在两侧。
- 某侧为空时不能读取其栈顶，应从另一侧继续取值。
- 前驱弹出后补左子树右链，后继弹出后补右子树左链，方向不能写反。
- 只弹栈而不展开对应子树，会漏掉后续仍可能更近的值。
- 遍历全树后再建堆，不属于只访问与
h + k相关节点的按需解法。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 658. 找到 K 个最接近的元素 | 中等 | 中序展开后就是有序数组中找最近 k 个元素，可直接对照窗口的端点淘汰原则。 |
| 173. 二叉搜索树迭代器 | 中等 | 双栈解把受控中序遍历分别向前、向后推进，避免提前保存全部节点。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！