Closest BST value
- Easy
- keyword: Recursion, Top-down, Bottom-up
- 类似: LCA, Tree diameter
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
- Given target value is a floating point.
- You are guaranteed to have only one unique value in the BST that is closest to the target.
idea
- 看到树自然就想到recursion, 因为Tree本身就是一个recursion结构, 不管是build, update, search都是recursion.
- 熟练掌握DFS/BFS, 以及pre/in/post. 当然遍历也可以用iteration写出来, 特别是FB会问到: 一道题目的递归/iteration写法.
- 一道题当然是要找规律和性质, 不要想一步做出来. 这里可以看到: 题目给出的TreeNode的val是int. 那么有什么情况呢?
- 如果和root相等, 即root.val转化为double和target相等, 直接返回.
- 如果不等有2种情况:
- 小于root, 那么向左儿子递归.
- 大于root, 那么向右儿子递归.
- 由于target有可能比儿子更靠近父亲, 所以最后的结果是: $$Math.min(Math.abs(root-target) - Math.abs(kid-target)$$. 关键的是这个怎么update呢? 是放在recursion中作为param吗(正如我第一次写)
方法1: going-down the tree
- 我第一次写的方法是pre-order, 即不断向下, update 最接近的node和val. 然后到了null就返回val. 这需要递归的过程中保存
double[] diff, int[] ans
, 从而保证每一次向下走都是有效的update. - 例子:
target = 7.123
9
/ \
/ \
4 15
/ \
3 6
方法2: go-up the tree
- 参考了Leetcode discuss, 发现这个简洁的方法. 即找到root以及对应subtree(只会选其中一个子树)中最接近的val即可. 所以是向上走的时候update(return). 为什么呢? 因为子树只有遍历完才会有整个subtree最接近target的val, 从而和root比较.
- 代码如下:
public int rec(TreeNode root, double target) {
int a = root.val;
TreeNode kid = root.val < target ? root.right : root.left;
if (kid == null) {
return a;
}
int b = rec(kid, target); // recursion call之后的是go-up tree. 好好理解!!!
return (Math.abs(a-target) < Math.abs(b - target) ? a : b;
}
错误总结
- 不要把大type转化为小type, 这样会丢失信息: 例如我一开始把target cast为int赖和root.val比较. 得到了2 = 2.833的情况=>导致了选3的左儿子: 1, 而不是3.
写后感
- 加深理解go-up tree的recursion写法.