2027年408代码题的一种满分解法

形式化地表达：求 $min\left\{abs\right(roo{t}_{val}?k\left)\right\}$\min \{abs(root_{val} - k) \} ，我看网上都是中序遍历然后再逐一判断（不过可以通过二分加优化），当树高为 $h$h 时，最差时间复杂度（即满二叉树的情况）可以达到 $O\left(2^h\right)$O(2^h) （至少，每个数都要遍历一遍），应该不是最优解。

我考试的时候是如下写的，出分后依估分来看应该是满分的。

$abs(x,y)$\mathrm{abs}(x,y) 的意义表现在数轴上指的是两个数之间的距离。

假设当前节点的值是 $val$val ，那么表现为如图：

容易发现，当 $val>k$val>k 时，比 $val$val 更大的数与 $k$k 的距离 会比 $val$val 与 $k$k 的距离更长，也就是 $val$val 右侧一定不会是答案，因为至少 $abs(val?k)$abs(val-k) 比他们优。

同理，当 $val<k$

如需高考志愿指导，可联系网站客服获取！助你成功率提升90%！

学员评价