LeetCode 270. 最接近的二叉搜索树值

2026-09-13 HGNULB 约 4 分钟

文章信息 2 个分类 5 个标签

分类

LeetCode 简单

题目描述

✅ 270. 最接近的二叉搜索树值

题意分析

在一棵非空二叉搜索树中，寻找与浮点目标 target 绝对距离最小的节点值；如果两个候选距离相同，返回其中较小的值。

目标不一定是整数，也不一定存在于树中，因此本题不是只判断能否命中某个键。结果必须取自实际节点，需要在利用二叉搜索树缩小搜索范围的同时，保留途中见到的最佳候选。

解法：沿搜索路径维护最近值

核心思路

[!blue]

用根节点的值初始化 answer，它一定是树中真实存在的候选。每到一个节点，比较当前值和已有答案分别到目标的绝对距离：当前更近就替换；距离相等时，仅在当前值更小时替换。这样 answer 始终符合已经访问过的节点中的最优选择规则。

接下来利用二叉搜索树排除一侧。若目标小于当前节点值，右子树中的值都不小于当前值，它们到目标的距离只会更大或相同，当前节点已经是不差的候选，所以右子树不可能带来需要保留的新答案，只需进入左子树。

若目标大于当前值，左子树同理不可能比当前节点更接近目标，只需进入右子树。精确命中时距离为零，已是最小可能距离，代码即使继续按既定方向向下，也不会丢掉这个答案。

每次排除的子树都已经被当前候选支配，因此只沿一条搜索路径访问，就足以覆盖所有可能改善答案的位置。走到空节点时已没有未检查的可行方向，返回沿途记录的最优值。

搜索方向与答案比较是两件事：前者由目标和当前键的大小关系决定，后者由绝对距离和等距规则决定。不能只返回搜索停止前的最后一个节点，因为更早的祖先也可能更接近目标。

解题步骤

用非空根的值初始化答案。

当前节点非空时，比较距离，按“更近优先、等距取小值”更新答案。

目标小于当前值则进入左子树，否则进入右子树。

遍历结束后返回保留的候选值。

代码实现

class Solution {
    public int closestValue(TreeNode root, double target) {
        int answer = root.val;

        while (root != null) {
            double distance = Math.abs(root.val - target);
            double best = Math.abs(answer - target);

            if (distance < best || distance == best && root.val < answer) {
                answer = root.val;
            }

            root = target < root.val ? root.left : root.right;
        }

        return answer;
    }
}

import "math"

func closestValue(root *TreeNode, target float64) int {
    answer := root.Val
    for root != nil {
        distance, best := math.Abs(float64(root.Val)-target), math.Abs(float64(answer)-target)
        if distance < best || distance == best && root.Val < answer {
            answer = root.Val
        }
        if target < float64(root.Val) {
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return answer
}

复杂度分析

时间复杂度：$O(h)$，只沿一条从根向下的路径访问。树高为 h，平衡时为 $O(\log n)$，退化成链时最坏为 $O(n)$。

空间复杂度：$O(1)$，迭代维护当前节点和最佳值，不使用递归栈或遍历集合。

关键点总结

[!green]

先把当前节点纳入候选，再借它证明另一侧不可能更优，从而安全排除子树。

绝对距离决定是否更新答案，键的大小关系决定继续向哪一侧走。

等距规则需要显式比较值，不能依赖节点恰好被访问的先后。

易错点总结

[!yellow]

把浮点目标提前转换成整数，会改变真实距离和搜索方向。

只在距离严格变小时更新，没有处理等距取较小值，可能保留错误候选。

返回最后访问的节点，可能丢掉路径上更接近目标的祖先。

根据两个孩子表面的距离选择方向，不符合二叉搜索树整侧排除的依据，可能漏掉子树内部更近的节点。

把复杂度固定写成对数级，忽略二叉搜索树本身不保证平衡。

相似题目

题目	难度	关联与区别
700. 二叉搜索树中的搜索	简单	复用二叉搜索树的单路径搜索；本题沿途保留最近候选，而不是只找完全相等的值。
658. 找到 K 个最接近的元素	中等	从找一个最近值扩展到最近 k 个元素，有序性仍然用于排除更远候选。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/90578124

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！