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

Notice

• 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.

Example

Given root ={1}, target =4.428571, return1.

update 04/09 midnight

• [x] 用一个global variable, curt = root.val; traversal;
• [x] 最好直接把这个variable 带入为参数，见下面的解法；
• [x] if (root.val < target) { val = helper(root.right, target, val); }else if (root.val > target) { val = helper(root.left, target, val); }
• [x] divide and conquer， 用val作为返回值

public class Solution {
    /**
     * @param root: the given BST
     * @param target: the given target
     * @return: the value in the BST that is closest to the target
     */
    private int curt;
    public int closestValue(TreeNode root, double target) {
        // write your code here
        curt = root.val;
        helper(root, target);
        return curt;
    }
    private void helper(TreeNode root, double target) {
        if (root == null) {
            return;
        }
        helper(root.left, target);
        if (Math.abs(root.val-target) < Math.abs(curt - target)) {
            curt = root.val;
        }
        helper(root.right, target);

    }
}

/*
        BST只搜索一半就行
         if (root.val < target) {
            helper(root.right,target);
         }else{
            helper(root.left,target);
         }


*/

public class Solution {
    /**
     * @param root: the given BST
     * @param target: the given target
     * @return: the value in the BST that is closest to the target
     */
    public int closestValue(TreeNode root, double target) {
        // write your code here
        int ans = root.val;
        while (root != null) {
            if (Math.abs(root.val - target) < Math.abs(ans - target)) {
                ans = root.val;
            }
            root = (root.val > target ) ? root.left : root.right;
        }
        return ans;
    }
}

public class Solution {
    /**
     * @param root: the given BST
     * @param target: the given target
     * @return: the value in the BST that is closest to the target
     */
    public int closestValue(TreeNode root, double target) {
        // write your code here
        int ans = helper(root, target, root.val);
        return ans;
    }
    private int helper(TreeNode root, double target, int val) {
        if (root == null) {
            return val; //表示不更新
        }
        if (Math.abs(root.val - target) < Math.abs(val - target)) {
            val = root.val;
        }
        if (root.val < target) {
            val = helper(root.right, target, val);
        }else if (root.val > target) {
            val = helper(root.left, target, val);
        }
        return val;
    }

}