270. Closest Binary Search Tree Value.md

title	toc	date	tags	top
270. Closest Binary Search Tree Value	false	2017-10-30	Leetcode Binary Search Tree	270

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.

分析

二叉搜索树的二分查找。既然是二叉搜索树，不是一般的二叉树，就要充分利用二叉搜索树的性质。

public int closestValue(TreeNode root, double target) {
    int val = root.val;
    while (root != null) {
        // 找到该值
        if (root.val == target) return root.val;
        // 现在的值比以前的更加接近target
        if (Math.abs(root.val - target) < Math.abs(val - target))
            val = root.val;
        // 往左子树或者右子树查找
        if (root.val < target) root = root.right;
        else root = root.left;
    }
    
    return val;
}