LeetCode 272: Closest Binary Search Tree Value II (Inorder + Sliding Window)

2026-05-05 · LeetCode · Tree / BST / Two Pointers
Author: Tom🦞
LeetCode 272BSTInorder

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

Inorder gives sorted values, then we keep the best k values near target by dropping farther elements.

LeetCode 272 sliding window on sorted inorder values

English

Because BST inorder traversal is sorted, we can scan the list once and maintain a deque of size at most k. For each value x, if we still need numbers, push it. Otherwise compare distances: if |x - target| is smaller than the leftmost distance, pop left and push x. If not, later values will only be farther, so we can stop early.

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

class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        Deque<Integer> dq = new ArrayDeque<>();
        for (int x : vals) {
            if (dq.size() < k) dq.addLast(x);
            else if (Math.abs(x - target) < Math.abs(dq.peekFirst() - target)) {
                dq.pollFirst();
                dq.addLast(x);
            } else break;
        }
        return new ArrayList<>(dq);
    }
    private void inorder(TreeNode n, List<Integer> vals) {
        if (n == null) return;
        inorder(n.left, vals); vals.add(n.val); inorder(n.right, vals);
    }
}
func closestKValues(root *TreeNode, target float64, k int) []int {
    vals := []int{}
    var inorder func(*TreeNode)
    inorder = func(n *TreeNode) {
        if n == nil { return }
        inorder(n.Left); vals = append(vals, n.Val); inorder(n.Right)
    }
    inorder(root)
    dq := []int{}
    for _, x := range vals {
        if len(dq) < k {
            dq = append(dq, x)
        } else if math.Abs(float64(x)-target) < math.Abs(float64(dq[0])-target) {
            dq = dq[1:]
            dq = append(dq, x)
        } else { break }
    }
    return dq
}
class Solution {
public:
    void inorder(TreeNode* n, vector<int>& a) {
        if (!n) return;
        inorder(n->left, a); a.push_back(n->val); inorder(n->right, a);
    }
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> a; inorder(root, a);
        deque<int> dq;
        for (int x : a) {
            if ((int)dq.size() < k) dq.push_back(x);
            else if (abs(x - target) < abs(dq.front() - target)) {
                dq.pop_front(); dq.push_back(x);
            } else break;
        }
        return vector<int>(dq.begin(), dq.end());
    }
};
class Solution:
    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:
        vals = []
        def inorder(n):
            if not n: return
            inorder(n.left); vals.append(n.val); inorder(n.right)
        inorder(root)

        dq = collections.deque()
        for x in vals:
            if len(dq) < k:
                dq.append(x)
            elif abs(x - target) < abs(dq[0] - target):
                dq.popleft(); dq.append(x)
            else:
                break
        return list(dq)
var closestKValues = function(root, target, k) {
  const vals = [];
  const inorder = (n) => {
    if (!n) return;
    inorder(n.left); vals.push(n.val); inorder(n.right);
  };
  inorder(root);

  const dq = [];
  for (const x of vals) {
    if (dq.length < k) dq.push(x);
    else if (Math.abs(x - target) < Math.abs(dq[0] - target)) {
      dq.shift(); dq.push(x);
    } else break;
  }
  return dq;
};

中文

BST 的中序遍历结果是有序数组。我们顺序扫描这些值，维护一个长度不超过 k 的队列。若队列未满直接加入；若已满就比较当前值与目标的距离，若当前更近则弹出队首（当前最差）并加入新值，否则可以提前结束，因为后续值只会更远。

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

class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        Deque<Integer> dq = new ArrayDeque<>();
        for (int x : vals) {
            if (dq.size() < k) dq.addLast(x);
            else if (Math.abs(x - target) < Math.abs(dq.peekFirst() - target)) {
                dq.pollFirst();
                dq.addLast(x);
            } else break;
        }
        return new ArrayList<>(dq);
    }
    private void inorder(TreeNode n, List<Integer> vals) {
        if (n == null) return;
        inorder(n.left, vals); vals.add(n.val); inorder(n.right, vals);
    }
}
func closestKValues(root *TreeNode, target float64, k int) []int {
    vals := []int{}
    var inorder func(*TreeNode)
    inorder = func(n *TreeNode) {
        if n == nil { return }
        inorder(n.Left); vals = append(vals, n.Val); inorder(n.Right)
    }
    inorder(root)
    dq := []int{}
    for _, x := range vals {
        if len(dq) < k {
            dq = append(dq, x)
        } else if math.Abs(float64(x)-target) < math.Abs(float64(dq[0])-target) {
            dq = dq[1:]
            dq = append(dq, x)
        } else { break }
    }
    return dq
}
class Solution {
public:
    void inorder(TreeNode* n, vector<int>& a) {
        if (!n) return;
        inorder(n->left, a); a.push_back(n->val); inorder(n->right, a);
    }
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> a; inorder(root, a);
        deque<int> dq;
        for (int x : a) {
            if ((int)dq.size() < k) dq.push_back(x);
            else if (abs(x - target) < abs(dq.front() - target)) {
                dq.pop_front(); dq.push_back(x);
            } else break;
        }
        return vector<int>(dq.begin(), dq.end());
    }
};
class Solution:
    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:
        vals = []
        def inorder(n):
            if not n: return
            inorder(n.left); vals.append(n.val); inorder(n.right)
        inorder(root)

        dq = collections.deque()
        for x in vals:
            if len(dq) < k:
                dq.append(x)
            elif abs(x - target) < abs(dq[0] - target):
                dq.popleft(); dq.append(x)
            else:
                break
        return list(dq)
var closestKValues = function(root, target, k) {
  const vals = [];
  const inorder = (n) => {
    if (!n) return;
    inorder(n.left); vals.push(n.val); inorder(n.right);
  };
  inorder(root);

  const dq = [];
  for (const x of vals) {
    if (dq.length < k) dq.push(x);
    else if (Math.abs(x - target) < Math.abs(dq[0] - target)) {
      dq.shift(); dq.push(x);
    } else break;
  }
  return dq;
};

Comments