Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/270.html

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.

 

Example 1:

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

Example 2:

Input: root = [1], target = 4.428571
Output: 1

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• 0 <= Node.val <= 109
• -109 <= target <= 109

Algorithm

Use the characteristics of the binary search tree (left<root<right) to quickly locate, because the root node is an intermediate value,

When we traverse down, we compare according to the relationship between the target value and the value of the root node.

If the target value is less than the node value, we should find a smaller value, so we go to the left subtree to find, otherwise we go to the right subtree to find.

Code

• Java
• C++
• Python
• Go
• Javascript

• 
  public class Closest_Binary_Search_Tree_Value {
  
      /**
       * Definition for a binary tree node.
       * public class TreeNode {
       *     int val;
       *     TreeNode left;
       *     TreeNode right;
       *     TreeNode(int x) { val = x; }
       * }
       */
  
      public class Solution {
  
          public int closestValue(TreeNode root, double target) {
  
              TreeNode child = target < root.val ? root.left : root.right;
  
              if (child == null) {
                  return root.val;
              }
  
              int childClosest = closestValue(child, target);
  
              return Math.abs(root.val - target) < Math.abs(childClosest - target) ? root.val : childClosest;
          }
      }
  }
  
  ############
  
  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode() {}
   *     TreeNode(int val) { this.val = val; }
   *     TreeNode(int val, TreeNode left, TreeNode right) {
   *         this.val = val;
   *         this.left = left;
   *         this.right = right;
   *     }
   * }
   */
  class Solution {
      public int closestValue(TreeNode root, double target) {
          int ans = root.val;
          double mi = Double.MAX_VALUE;
          while (root != null) {
              double t = Math.abs(root.val - target);
              if (t < mi) {
                  mi = t;
                  ans = root.val;
              }
              if (root.val > target) {
                  root = root.left;
              } else {
                  root = root.right;
              }
          }
          return ans;
      }
  }
  

• // OJ: https://leetcode.com/problems/closest-binary-search-tree-value/
  // Time: O(N)
  // Space: O(logN)
  class Solution {
  public:
      int closestValue(TreeNode* root, double target) {
          double dist = abs(target - root->val);
          if (dist < .5) return root->val;
          if (root->val < target) {
              if (!root->right) return root->val;
              int right = closestValue(root->right, target);
              return dist < abs(target - right) ? root->val : right;
          }
          if (!root->left) return root->val;
          int left = closestValue(root->left, target);
          return dist < abs(target - left) ? root->val : left;
      }
  };
  

• # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
    def closestValue(self, p, target):
      """
      :type root: TreeNode
      :type target: float
      :rtype: int
      """
      ans = p.val
      while p:
        if abs(target - p.val) < abs(ans - target):
          ans = p.val
        if target < p.val:
          p = p.left
        else:
          p = p.right
      return ans
  
  
  ############
  
  # 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: Optional[TreeNode], target: float) -> int:
          ans, mi = root.val, inf
          while root:
              t = abs(root.val - target)
              if t < mi:
                  mi = t
                  ans = root.val
              if root.val > target:
                  root = root.left
              else:
                  root = root.right
          return ans
  
  

• /**
   * Definition for a binary tree node.
   * type TreeNode struct {
   *     Val int
   *     Left *TreeNode
   *     Right *TreeNode
   * }
   */
  func closestValue(root *TreeNode, target float64) int {
  	ans := root.Val
  	mi := math.MaxFloat64
  	for root != nil {
  		t := math.Abs(float64(root.Val) - target)
  		if t < mi {
  			mi = t
  			ans = root.Val
  		}
  		if float64(root.Val) > target {
  			root = root.Left
  		} else {
  			root = root.Right
  		}
  	}
  	return ans
  }
  

• /**
   * Definition for a binary tree node.
   * function TreeNode(val, left, right) {
   *     this.val = (val===undefined ? 0 : val)
   *     this.left = (left===undefined ? null : left)
   *     this.right = (right===undefined ? null : right)
   * }
   */
  /**
   * @param {TreeNode} root
   * @param {number} target
   * @return {number}
   */
  var closestValue = function (root, target) {
      let ans = root.val;
      let mi = Number.MAX_VALUE;
      while (root) {
          const t = Math.abs(root.val - target);
          if (t < mi) {
              mi = t;
              ans = root.val;
          }
          if (root.val > target) {
              root = root.left;
          } else {
              root = root.right;
          }
      }
      return ans;
  };
  
  

All Problems

All Solutions