270. Closest Binary Search Tree Value

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.

Solution

Recursive Binary search, time O(logn), space O(1)

写起来略繁琐，不如下面的iterative写法。注意不要把diff强转成int，可能会overflow。

/**
 * 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) {
        if (root.left == null && root.right == null) {
            return root.val;
        }
        
        boolean childrenSearched = false;
        int childrenValue = 0;
        
        if (root.val < target && root.right != null) {
            childrenSearched = true;
            childrenValue = closestValue(root.right, target);
        } else if (root.val > target && root.left != null) {
            childrenSearched = true;
            childrenValue = closestValue(root.left, target);
        }
        
        int closest = root.val;
        if (childrenSearched 
            && Math.abs(childrenValue - target)     // compare double to avoid overflow
            < Math.abs(closest - target)) {
            closest = childrenValue;
        }
        
        return closest;
    }
}

Iterative Binary search

非常简洁的写法，喜欢。

/**
 * 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) {
        int closest = root.val;
        
        while (root != null) {
            if (Math.abs(root.val - target) < Math.abs(closest - target)) {
                closest = root.val;
            }
            root = root.val < target ? root.right : root.left;
        }
        
        return closest;
    }
}