图 1：本文封面，点明题目与优化方向。
先说明属性：这是一篇经典题解析，题目出自本地历史面试资料，与任何公司的当前招聘无关。「二叉搜索树中找第 K 小的节点」是树结构面试的高频题——基础解法人尽皆知，区分度全在追问里：还能再快吗？代价是什么？
想象面试现场，面试官画出一棵二叉搜索树：根 5，左子 3、右子 7，叶子 2、4、6、8。问：找出第 3 小的节点。
第一步，基础回答：中序遍历，数到第 K 个就停。
二叉搜索树有一个天造地设的性质：中序遍历（左、根、右）的输出天然是升序。所以对这棵树做中序遍历，序列是 2、3、4、5、6、7、8，第 K 小就是序列里的第 K 个——k=3 时答案是 4。
实现上用迭代加显式栈，并且「数到第 K 个立刻返回」，不做无谓的完整遍历。代价是：从根走到最左要压栈 h 层（h 是树高），之后最多再访问 K 个节点，时间复杂度 O(h + K)，空间 O(h)。平衡树里 h 是 log n，这个解法已经足够好，也是面试官期待的第一反应。
第二步，进阶回答：节点上挂左子树大小，按秩查找。
面试官追问来了：「如果这棵树要被反复查询第 K 小，每次都遍历计数，能不能更快？」
能。思路是给每个节点预先记录一个 leftSize——它左子树的节点个数。查找时拿着 K 和 leftSize + 1 比较：相等，当前节点就是答案；K 更小，答案在左子树，往左走；K 更大，答案在右子树，往右走并且把 K 减去 leftSize + 1（左子树和根已经跳过了）。
拿示例树查 k=3 走一遍：根 5 的 leftSize=3，3 小于 3+1，往左到节点 3；节点 3 的 leftSize=1，3 大于 1+1，往右且 k 变成 3-2=1；节点 4 的 leftSize=0，k=1 正好等于 0+1，命中，答案是 4。全程只沿一条根到叶的路径走，时间复杂度 O(h)——不再依赖 K 的大小。
代价也必须主动交代：插入和删除节点时，路径上每个祖先的 leftSize 都要维护，写操作从 O(h) 变成了带维护负担的 O(h)。所以这是典型的「以写换读」——查询频繁选按秩查找，偶尔查一次选中序遍历就够了。
第三步，写出可运行的代码。
下面这份实现把两种解法放在同一棵树上对比，并统计各自实际访问的节点数，用 Node.js 22.15.0 直接运行（node kth-smallest.js）即可：
'use strict';
// 建树：根 5，左子 3 右子 7，叶子 2、4、6、8
function node(val, left = null, right = null) {
return { val, left, right, leftSize: 0 };
}
const root = node(5, node(3, node(2), node(4)), node(7, node(6), node(8)));
// 为每个节点预计算左子树大小 leftSize
function fillLeftSize(n) {
if (!n) return 0;
const l = fillLeftSize(n.left);
const r = fillLeftSize(n.right);
n.leftSize = l;
return l + r + 1;
}
fillLeftSize(root);
// 方案一：迭代中序遍历，数到第 K 个提前停止
let inorderVisits = 0;
function kthByInorder(root, k) {
const stack = [];
let curr = root;
while (curr || stack.length) {
while (curr) { stack.push(curr); curr = curr.left; }
curr = stack.pop();
inorderVisits++;
if (--k === 0) return curr.val;
curr = curr.right;
}
return null;
}
// 方案二：按秩查找，沿 leftSize 与 K 的比较走一条路径
let selectVisits = 0;
function kthBySelect(n, k) {
while (n) {
selectVisits++;
if (k === n.leftSize + 1) return n.val;
if (k <= n.leftSize) n = n.left;
else { k -= n.leftSize + 1; n = n.right; }
}
return null;
}
for (const k of [1, 3, 7]) {
inorderVisits = 0; selectVisits = 0;
const a = kthByInorder(root, k);
const b = kthBySelect(root, k);
console.log(`k=${k}：中序遍历得 ${a}（访问 ${inorderVisits} 个节点），按秩查找得 ${b}（访问 ${selectVisits} 个节点）`);
}
实测输出如下：
k=1：中序遍历得 2（访问 1 个节点），按秩查找得 2（访问 3 个节点）
k=3：中序遍历得 4（访问 3 个节点），按秩查找得 4（访问 3 个节点）
k=7：中序遍历得 8（访问 7 个节点），按秩查找得 8（访问 3 个节点）
两种解法答案一致，访问次数的差异正是复杂度的具象化：k 越大，中序遍历要数的节点越多；按秩查找永远只走一条路径，三次访问封顶（这棵树高为 3）。k=1 时按秩查找反而多走一步——优化从来不是无条件的。
图 2：中序遍历按序计数，按秩查找沿路径直达。
可能的追问。
「树不平衡怎么办？」中序遍历的代价涨到 O(n)，按秩查找的路径也变长，该引平衡机制引平衡机制——leftSize 的维护可以和旋转一起做。「要支持动态插入删除还有别的结构吗？」平衡树的每个节点维护子树大小，就是教科书里的顺序统计树，思路上一脉相承。
易错点清单。
一，忘记二叉搜索树的中序遍历才是升序——前序、层序都不是，性质用错全盘皆输。二，遍历找到答案后不提前停止，白付 O(n)。三，按秩查找往右走时忘记把 K 减去 leftSize + 1，答案整体错位。四，只讲优化不讲维护代价，被「插入删除怎么办」问住。
回到面试现场，建议的答题节奏：先点破「中序遍历天然升序」这条性质，给出提前停止的迭代写法与复杂度，再主动把「频繁查询」的优化方向递出去——挂 leftSize 按秩查找，同时交代写操作的维护代价。有序结构中按秩查找是检索系统的基本功，特征索引、排行榜存储都在「遍历顺序与剪枝」上做文章。
你在面试里被「还能再优化吗」追问到时，是怎么接住的？欢迎分享你的经历。