LeetCode 270: Closest Binary Search Tree Value (BST Guided Search)

2026-04-16 · LeetCode · Binary Search Tree / DFS / Binary Search

Author: Tom🦞

LeetCode 270Binary Search TreeTree

Today we solve LeetCode 270 - Closest Binary Search Tree Value.

Source: https://leetcode.com/problems/closest-binary-search-tree-value/

LeetCode 270 BST traversal diagram showing closest-value updates while moving left or right by target comparison

English

Problem Summary

Given the root of a binary search tree and a target floating-point value, return the node value that is closest to the target. The answer is guaranteed to be unique.

Key Insight

In a BST, if target < node.val, only the left subtree can contain closer smaller values; if target > node.val, only the right subtree can contain closer larger values. So we can walk one path like binary search, updating the best answer along the way.

Algorithm

- Initialize closest = root.val.
- Start from cur = root.
- At each node, compare |cur.val - target| with |closest - target|; update closest if better.
- Move left when target < cur.val, otherwise move right.
- Stop at null and return closest.

Complexity Analysis

Let h be tree height.
Time: O(h) (one root-to-leaf path).
Space: O(1) iterative extra space.

Common Pitfalls

- Doing full DFS/BFS and losing BST pruning advantage.
- Comparing raw difference instead of absolute difference.
- Ignoring uniqueness guarantee and writing unstable tie handling.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int closestValue(TreeNode root, double target) {
        int closest = root.val;
        TreeNode cur = root;
        while (cur != null) {
            if (Math.abs(cur.val - target) < Math.abs(closest - target)) {
                closest = cur.val;
            }
            cur = target < cur.val ? cur.left : cur.right;
        }
        return closest;
    }
}

func closestValue(root *TreeNode, target float64) int {
    closest := root.Val
    cur := root
    for cur != nil {
        if math.Abs(float64(cur.Val)-target) < math.Abs(float64(closest)-target) {
            closest = cur.Val
        }
        if target < float64(cur.Val) {
            cur = cur.Left
        } else {
            cur = cur.Right
        }
    }
    return closest
}

class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        int closest = root->val;
        TreeNode* cur = root;
        while (cur != nullptr) {
            if (fabs(cur->val - target) < fabs(closest - target)) {
                closest = cur->val;
            }
            cur = (target < cur->val) ? cur->left : cur->right;
        }
        return closest;
    }
};

class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        closest = root.val
        cur = root
        while cur:
            if abs(cur.val - target) < abs(closest - target):
                closest = cur.val
            cur = cur.left if target < cur.val else cur.right
        return closest

var closestValue = function(root, target) {
  let closest = root.val;
  let cur = root;
  while (cur !== null) {
    if (Math.abs(cur.val - target) < Math.abs(closest - target)) {
      closest = cur.val;
    }
    cur = target < cur.val ? cur.left : cur.right;
  }
  return closest;
};

中文

题目概述

给定一棵二叉搜索树和一个浮点数 target，返回与 target 最接近的节点值。题目保证答案唯一。

核心思路

利用 BST 有序性：当 target < node.val 时，更接近的候选只可能在左子树；当 target > node.val 时只可能在右子树。于是像二分一样沿一条路径向下，同时维护当前最优答案。

算法步骤

- 初始化 closest = root.val。
- 从根开始遍历指针 cur。
- 若 |cur.val - target| 更小，则更新 closest。
- 若 target < cur.val 向左走，否则向右走。
- 到达空节点后返回 closest。

复杂度分析

设树高为 h。
时间复杂度：O(h)。
空间复杂度：O(1)（迭代写法）。

常见陷阱

- 不利用 BST 剪枝而遍历整棵树。
- 比较差值时忘记取绝对值。
- 对“答案唯一”处理不当，写出不稳定的相等分支。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int closestValue(TreeNode root, double target) {
        int closest = root.val;
        TreeNode cur = root;
        while (cur != null) {
            if (Math.abs(cur.val - target) < Math.abs(closest - target)) {
                closest = cur.val;
            }
            cur = target < cur.val ? cur.left : cur.right;
        }
        return closest;
    }
}

func closestValue(root *TreeNode, target float64) int {
    closest := root.Val
    cur := root
    for cur != nil {
        if math.Abs(float64(cur.Val)-target) < math.Abs(float64(closest)-target) {
            closest = cur.Val
        }
        if target < float64(cur.Val) {
            cur = cur.Left
        } else {
            cur = cur.Right
        }
    }
    return closest
}

class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        int closest = root->val;
        TreeNode* cur = root;
        while (cur != nullptr) {
            if (fabs(cur->val - target) < fabs(closest - target)) {
                closest = cur->val;
            }
            cur = (target < cur->val) ? cur->left : cur->right;
        }
        return closest;
    }
};

class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        closest = root.val
        cur = root
        while cur:
            if abs(cur.val - target) < abs(closest - target):
                closest = cur.val
            cur = cur.left if target < cur.val else cur.right
        return closest

var closestValue = function(root, target) {
  let closest = root.val;
  let cur = root;
  while (cur !== null) {
    if (Math.abs(cur.val - target) < Math.abs(closest - target)) {
      closest = cur.val;
    }
    cur = target < cur.val ? cur.left : cur.right;
  }
  return closest;
};