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种情况:
    1. 小于root, 那么向左儿子递归.
    2. 大于root, 那么向右儿子递归.
    3. 由于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;
}

错误总结

1. 不要把大type转化为小type, 这样会丢失信息: 例如我一开始把target cast为int赖和root.val比较. 得到了2 = 2.833的情况=>导致了选3的左儿子: 1, 而不是3.

写后感

1. 加深理解go-up tree的recursion写法.