复盘 · LC 230 二叉搜索树中第K小的元素

题目

• 题号：LeetCode 230
• 名称：二叉搜索树中第 K 小的元素（Kth Smallest Element in a BST）
• 难度：Medium
• 链接：leetcode.cn/problems/kth-smallest-element-in-a-bst
• 今日代码：230-二叉搜索树中第K小的元素/index.js

题意

给定 BST 与整数 k，返回其中第 k 小的节点值（1-indexed）。

• BST 中序遍历即升序。
• 约束保证 k 合法。

涉及算法

标签	一句话
中序遍历	左 → 根 → 右，第 k 次访问即答案
剪枝	找到后提前 return，少走右子树

教程对照：18 · BFS 层序与 BST、16 · 二叉树遍历。

评价我的解法

中序计数，命中 k 后记录并停止——主路径正确。

我的代码（摘自 230-二叉搜索树中第K小的元素/index.js，不含本地测例）：

var kthSmallest = function (root, k) {
  let i = 0;
  let res = null;
  function preOrder(root) {
    if (res) {
      return;
    }
    if (!root) {
      return null;
    }
    preOrder(root.left);
    i++;
    if (i === k) {
      res = root.val;
      return;
    }
    preOrder(root.right);
  }
  preOrder(root);
  return res;
};

评价：

1. 套路对：BST + 第 k 小 = 中序第 k 个；有提前停止，比先收集整数组再取下标好。
2. 命名错误：又是 preOrder，实际是中序——和 199 同一问题，面试会减分。
3. if (res) 遇 0 失效：若第 k 小是 0，res = 0 后 if (res) 为假，剪枝失效（仍可能多走右子树）；返回值碰巧还是 0 能对，但边界不严谨。应用 found 标志或 res !== null（若允许 null 作未找到）。
4. 复杂度：平均/最好可早停；最坏仍 O(n) 时间、O(h) 栈。

小结：BST 中序用法今天两题（98、230）连上了；把命名和 0 假值坑改掉就稳。

最佳题解

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (root, k) {
  let count = 0;
  let ans = 0;
  let found = false;
  function inorder(node) {
    if (!node || found) return;
    inorder(node.left);
    if (found) return;
    count++;
    if (count === k) {
      ans = node.val;
      found = true;
      return;
    }
    inorder(node.right);
  }
  inorder(root);
  return ans;
};

• 时间 O(h + k) 量级（早停时），最坏 O(n)；空间 O(h)。
• 进阶：若频繁查询，可给节点维护子树规模做类似树状选择。

关联题目

题	为何相关
98. 验证二叉搜索树	同一中序有序性
94. 二叉树的中序遍历	模板题
285. 二叉搜索树中的中序后继	中序邻居（会员题，知套路即可）

一句话带走

BST 第 k 小：中序走，数到 k 就停——别用前序命名，剪枝别用真值判断 0。