[抄题]:
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
[暴力解法]:
时间分析:
空间分析:
[奇葩输出条件]:
[奇葩corner case]:
[思维问题]:
以为要用主函数+ DFS来做。错了,“最近”还是直接用二分法左右查找得了
[一句话思路]:
定义一个res,如果root离target的距离小 就替换成为新的res
尾递归变迭代 写法更清楚简单
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- 再次出错DFS的表达式不能用作赋值(因为会继续循环),所以只能用root赋值
[二刷]:
[三刷]:
[四刷]:
[五刷]:
[五分钟肉眼debug的结果]:
[总结]:
DFS的表达式不能用作赋值(因为会继续循环)
[复杂度]:Time complexity: O(lgn) Space complexity: O(n)
[英文数据结构或算法,为什么不用别的数据结构或算法]:
找最接近的值:用二分法
[关键模板化代码]:
while类型的dfs还是符合退出+扩展
while (root != null) { //exit if (Math.abs(target - root.val) < Math.abs(target - ans)) { ans = root.val; } //expand to left, right root = (root.val > target) ? root.left : root.right; }
[其他解法]:
[Follow Up]:
[LC给出的题目变变变]:
272. Closest Binary Search Tree Value II 最接近的k个数:俩stack 好吧。。
[代码风格] :
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int closestValue(TreeNode root, double target) { //ini int ans = root.val; //while while (root != null) { //exit if (Math.abs(target - root.val) < Math.abs(target - ans)) { ans = root.val; } //expand to left, right root = (root.val > target) ? root.left : root.right; } //return return ans; } }