ClosestBinarySearchTreeValue [source code]

public class ClosestBinarySearchTreeValue {
static
/******************************************************************************/
public class Solution {
    public int closestValue(TreeNode root, double target) {
        return helper(root, target, null);
    }

    private int helper(TreeNode root, double target, Integer minVal) {
        if (root == null) return minVal;
        if (minVal == null) minVal = root.val;
        double diff = Math.abs(target - root.val);
        if (diff < Math.abs(target - minVal)) minVal = root.val;
        int left = helper(root.left, target, minVal);
        if (Math.abs(target - left) < Math.abs(target - minVal)) minVal = left;
        int right = helper(root.right, target, minVal);
        if (Math.abs(target - right) < Math.abs(target - minVal)) minVal = right;
        return minVal;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ClosestBinarySearchTreeValue.Solution tester = new ClosestBinarySearchTreeValue.Solution();
    }
}

这题哪个 traversal order 其实都无所谓;

另外这一题的难点其实在于 minVal 一开始的初始化, 你选什么都不对. 这个题目的 target 之所以要选择可以用double, 就是为了让target 可以拥有超过 int 的上下界的值. 这样无论你把 minVal 初始化到上下那个边界, 他都可以直接让 target 等于这个边界(在 testcase 里面); 这样你的 minVal 始终就不会被更新, 这个就是一个false hit;

刚开始想了半天没有想明白这个问题怎么解决, 后来想了想还是要用 Null 来解决, 把 minVal 的 type 从 int 改成 Integer, 这样就可以检查初始情况, 也避免了初始值影响后面的update;

最后的速度不是很理想2(4). 这个是一个 BST, 所以一个单纯的DFS 肯定不是最速的解法;

这个是 submission 的最优解:

public class Solution {  
    double minDiff = Double.MAX_VALUE;  
    int result = 0;  
    public int closestValue(TreeNode root, double target) {  
        helper(root, target);  
        return result;  
    }  

    private void helper(TreeNode root, double target){  
        if(root == null) return;  
        if(root.val == target){  
            result = root.val;  
            return;  
        }  
        if(Math.abs(root.val - target) < minDiff){  
            minDiff = Math.abs(root.val - target);  
            result = root.val;  
        }  
        if(target < root.val){  
            helper(root.left, target);  
        }  
        else{  
            helper(root.right, target);  
        }  
    }  
}

好像跟我的代码的思路差别也不大, 主要就是一个改动, 他维护 minDiff 而不是 minVal. 虽然这个思路我刚开始写这个代码的时候也想过, 不过后来放弃了, 感觉维护 minVal 的话显得简练一些. 不过这里看了他的代码之后, 可以看到维护 minVal 有两个好处:

1. 初始化问题解决了, 因为维护的是 diff, 所以直接就设置到最大值就行了, 没有维护 val 的时候的那么多烦心事; 话虽如此, 经历过这个问题在 val 上面的初始化之后, 也算是一个学习的机会;
2. 节省了很多计算, 因为我的代码实际上每一个 iteration 有好几次使用 abs, 这个如果你维护 diff 的话,是不需要进行的. abs 这个函数, 按理说还是带来了一些不必要的时间消耗;

另外注意到这个代码跟我代码有一个共同的地方是 recursive 返回值都是 minVal, 只不过我一直把这个 minVal 也顺带当做 accum 一起往下传, 他则是使用 global 来做; 这个最后的速度是0(63);

这个是discussion 上面利用了 BST 性质的一个解:

public int closestValue(TreeNode root, double target) {  
    int a = root.val;  
    TreeNode kid = target < a ? root.left : root.right;  
    if (kid == null) return a;  
    int b = closestValue(kid, target);  
    return Math.abs(a - target) < Math.abs(b - target) ? a : b;  
}

这个逻辑还是很清晰的; 跟普通的 DFS 比, 其实就是把搜索空间缩小到了一条 path; 然后最后一句完成一个寻找整个 path 上的最小值的作用; 实际计算的时候是从 path 最底下的那个 node 开始, 从下往上走一遍找到 abs 最小的一个;

Problem Description

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:
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.
Difficulty:Easy
Category:Algorithms
Acceptance:39.16%
Contributor: LeetCode
Companies
microsoft google snapchat
Related Topics
tree binary search
Similar Questions
Count Complete Tree Nodes Closest Binary Search Tree Value II