270. Closest Binary Search Tree Value

Description

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.

Hint

binary search

Method

Time & Space

o(logn)

Code

1

private double diff = Double.MAX\_VALUE;

   private TreeNode res = null;



// public int closestValue\(TreeNode root, double target\) {

//       traversal\(root, target\);

//       return res.val;

// }



// public void traversal\(TreeNode root, double target\){

//       if \(root == null\){

//           return;

//       }

//       if \(diff > Math.abs\(root.val - target\)\){

//           diff = Math.abs\(root.val - target\);

//           res = root;

//       } 

//       if \(target > root.val\){

//           traversal\(root.right, target\);

//       } else if \(target < root.val\){

//           traversal\(root.left, target\);

//       } else {

//           diff = 0.0;

//           return;

//       }

// }

2.

public int closestValue(TreeNode root, double target){

int res = root.val;

          while \(root != null\){

                     if \(Math.abs\(res - target\) > Math.abs\(root.val - target\)\){

                         res = root.val;

                     }

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

          }

          return res;

   }