My Java recursive solution


  • 0
    Z
    public int closestValue(TreeNode root, double target) {
        return closest(root,null,null,target);
    }
    // left is the left boundary ,right is right boudary. use binary search to find target
    // 1. root is null means the target value is not in the tree, check the left and right boundary to find 
    //    which is the closest one.
    // 2. find the target in the tree, just return the node's value.
    // 3. same idea of valid binary search tree.
    public int closest(TreeNode root,TreeNode left,TreeNode right,double target){
        if(root == null) {
            return helper(left,right,target);
        }
        if((double)root.val == target) return root.val;
        if(root.val > target){
            return closest(root.left,left,root,target);
        }else {
            return closest(root.right,root,right,target);
        }
    }
    // find which is closer
    public int helper(TreeNode left,TreeNode right,double target){
        if(left == null) return right.val;
        if(right == null) return left.val;
        double diff = right.val - target -(target-left.val);
        return diff >= 0?left.val:right.val;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.