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

/**
 * 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 res = root.val;
        while(root != null){
            if(Math.abs(target - root.val) < Math.abs(target - res)){
                res = root.val;
            }

            if(Math.abs(target - root.val) == Math.abs(target - res) && root.val < 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 abs(root.val - target) == abs(res - target) and root.val < res:
                res = root.val
            
            if root.val < target:
                root = root.right
            else:
                root = root.left
                
        return res