270. Closest Binary Search Tree Value

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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. Example:

Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4

Code

class Solution {
    public int closestValue(TreeNode root, double target) {
        int res = root.val;
        while(root != null){
            if(Math.abs(target - root.val) < Math.abs(target - res)){
                res = root.val;
            }

            root = root.val > target ? root.left : root.right;
        }

        return res;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        res = root.val

        while root:
            if abs(root.val - target) < abs(res - target):
                res = root.val

            if root.val < target:
                root = root.right
            else:
                root = root.left

        return res