270. Closest Binary Search Tree Value

Leetcode Binary Search Tree

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;
}