如何在二叉搜索树中找到最接近目标值的节点？

简化版

从根开始像普通 BST 搜索一样走，同时维护当前最接近 target 的答案。每到一个节点，就比较 abs(node.val - target) 和当前最小差值；如果 target 小于当前值就去左边，否则去右边。因为另一侧只会离目标方向更远，不必两边都搜。

详细版

BST 最近值的直觉是：搜索目标值时经过的路径，已经包含了最可能接近目标的候选节点。每次访问一个节点都更新答案，然后根据 target 与 node.val 的大小决定下一步。如果 target < node.val，更接近 target 的节点只可能在左子树；如果去右子树，值会更大，通常只会离 target 更远。反之同理。

代码可以用迭代实现，维护 ans 和 minDiff。当出现相同差值时，按题目约定返回较小值或任意值；如果题目没有说，面试中最好主动说明 tie-break。时间复杂度 O(h)，空间 O(1)。

完整版教学

一、这题和普通查找有什么不同

普通 BST 查找只关心是否存在等于 target 的节点；最近值查找则要求即使没有相等节点，也要返回差值最小的那个。例如树中有 1, 3, 4, 6, 8，目标是 5.2，答案是 6，因为 |6 - 5.2| = 0.8，而 |4 - 5.2| = 1.2。

values = [1, 3, 4, 6, 8]
target = 5.2
distance:
  4 -> 1.2
  6 -> 0.8
answer = 6

所以算法要做两件事：沿 BST 方向搜索；同时记录走过路径上的最佳候选。只搜索不记录，会在找不到等值节点时丢失答案。

二、为什么只走一条路径也够

假设当前节点值是 10，目标是 6.3。因为目标比 10 小，真正接近目标的节点如果还没遇到，大概率在左子树；右子树所有值都大于 10，它们离 6.3 至少比 10 更远。因此可以直接去左边，同时把 10 作为一个候选保留下来。

node.val = 10, target = 6.3
right subtree values > 10
任意 right 值 x: x - 6.3 > 10 - 6.3 = 3.7
所以右子树不可能比 10 更接近 target

这个推理依赖 BST 的全局有序性。每次只排除一侧，并不是贪心乱猜，而是利用“被排除那侧的所有值都在当前值外侧”的数学事实。

三、用路径模拟一遍

看下面这棵 BST，找最接近 target = 4.6 的节点。

        5
       / \
      3   8
     / \
    2   4

路径：5 -> 3 -> 4

访问 5 时，差值是 0.4，暂定答案 5；因为 4.6 < 5，去左边。访问 3 时，差值是 1.6，不更新；因为 4.6 > 3，去右边。访问 4 时，差值是 0.6，仍不更新；继续向右为空，结束。答案是 5。这个例子很适合说明：最终停下的叶子不一定是答案，必须维护全程最佳值。

四、标准迭代代码

代码要避免浮点比较写得含糊。可以维护 double bestDiff，每次访问都计算当前差值。如果题目要求差值相同返回较小值，就在相等时补 tie-break。

int closestValue(TreeNode root, double target) {
    int ans = root.val;
    double bestDiff = Math.abs(root.val - target);
    TreeNode cur = root;

    while (cur != null) {
        double diff = Math.abs(cur.val - target);
        if (diff < bestDiff || (diff == bestDiff && cur.val < ans)) {
            ans = cur.val;
            bestDiff = diff;
        }

        if (target < cur.val) {
            cur = cur.left;
        } else if (target > cur.val) {
            cur = cur.right;
        } else {
            return cur.val;
        }
    }
    return ans;
}

如果语言里浮点相等比较不稳定，tie-break 可以写成 Math.abs(diff - bestDiff) < 1e-12。不过很多面试题的输入能让直接比较通过，讲清楚意图即可。

五、和中序数组法的对比

这题也可以先中序遍历得到升序数组，再二分找插入位置，比较相邻两个数。但单次查询时，这样会多用 O(n) 空间，并且要遍历全树。路径搜索法只走树高 h，平衡时明显更轻。

方法	时间复杂度	空间复杂度	适用场景
中序数组 + 二分	O(n) 构建 + O(log n) 查询	O(n)	同一棵树大量查询且可缓存数组
单路径搜索	O(h)	O(1)	单次或少量查询
增强平衡树	O(log n)	结构额外维护	动态更新和大量查询

如果面试官问“多次 target 查询怎么办”，可以说明：若树不变，先中序转数组，再对每个 target 二分，整体会更划算；若树动态变化，则需要平衡树结构支持。

六、常见误区与追问

最近值题的关键不是走到哪里停，而是一路走一路更新最佳候选。

误区：最后搜索停下来的父节点一定是最近值。 不一定，路径上更早遇到的节点可能更接近，例如 target=4.6 时答案是 5，不是最后访问的 4。
误区：需要同时搜索左右子树。 BST 的有序性允许排除一侧，单路径搜索已经足够。
误区：只在空指针处才更新答案。 每访问一个节点都要更新，否则可能漏掉根或中间节点。
追问：差值相同返回谁？ 如果题目没约定，要主动说明；常见处理是返回较小值或任意一个。
追问：复杂度为什么是 O(h)？ 每层只走一个分支，最多走树高个节点。
追问：如果要找最接近的 k 个值呢？ 可以中序得到有序序列后双指针，或用两个栈分别维护前驱和后继。

七、加强记忆

BST 最近值可以理解成“带备忘录的搜索”：搜索方向仍然按 target < node.val 向左、target > node.val 向右，但每经过一个节点都要用差值更新答案。被排除的一侧不是随便放弃，而是因为它的所有值都在当前节点更外侧，不可能比当前节点更接近目标。回答时把“单路径 + 持续更新 + O(h)/O(1) + tie-break”说完整，就能覆盖主要考点。

简化版

详细版