Meta BST最接近目标：单路下降与并列值

题目重点：利用二叉搜索树次序寻找最接近target的值，并说明树高与有效BST前提。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

输入有效BST、有限数值target，返回最小绝对差值对应value；差相同取较小value，空树None。不是求K个最近节点。

解题路线

从root维护best，按(abs(value−target),value)字典序比较。target小于当前值只进入left，大于只进入right，相等立即返回。
为什么能剪掉另一侧？target<node时右子树值≥node，比target更远或同距，node已被比较；所以可能改善只在left。target>node对称，较小tie规则也不会丢更好候选。
单路遍历并不要求树平衡，复杂度由h决定。树退化成链仍O(N)，不可把普通BST查找总标O(log N)。
普通二叉树无排序性质则不能剪枝，必须全遍历；输入有NaN会破坏比较，本训练有限数值前提应保留。

手动走一遍

BST值[1,2,3,4]，target2.5同距2/3返回2；target−10返回最小1；target正好3可立即返回。空树不返回0避免与合法0值混淆。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class Node:
    def __init__(self,value,left=None,right=None):self.value=value;self.left=left;self.right=right


def closest_value(root,target):
    """Valid finite numeric BST; empty -> None, equal distance -> smaller value."""
    if root is None:return None
    best=root.value
    while root is not None:
        if (abs(root.value-target),root.value)<(abs(best-target),best):best=root.value
        if root.value==target:return root.value
        root=root.left if target<root.value else root.right
    return best

复杂度

O(h)时间/O(1)辅助空间；平衡树h=O(log N)，最坏O(N)。不构建inorder数组，后者需O(N)时间/空间但多次查询可二分权衡。

易错点与追问

容易失分的边界

把普通二叉树也按大小走单边会漏答案。
仅用差值<更新但遍历顺序未保证tie较小，可能输出3而非2。

继续深挖

重复值节点是否合法由BST合同决定，返回value相同不影响结果。
多target批查询时，什么时候值得预先inorder排序数组？