Question

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

 270	Closest Binary Search Tree Value

 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.

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

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

// 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

270 - Closest Binary Search Tree Value

Question

Algorithm

Code

All Problems

All Solutions