题目描述
思路解析动画文字版
核心一句话：BST 中序 = 升序，数到第 k 个就是第 K 小，提前停。
完整的 BST。中序遍历从最左下角开始，按「左子树 → 根 → 右子树」的顺序访问，每访问一个节点 count 加 1。
中序怎么找下一个？从根一路向左压栈，走到最左下角。当前定位到节点 1（它是所有未数节点里最小的），下一步把它计入。
中序走到当前最小的未访问节点 = 1（橙色）。它是目前 BST 里还没数过的最小值，准备把它计入：count 将变成 1。
节点 1 数完了，count = 1（蓝色=已计数）。升序序列变成 1。还没到第 6 个，继续中序走下一个更大的数。
中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 2（它是所有未数节点里最小的），下一步把它计入。
中序走到当前最小的未访问节点 = 2（橙色）。它是目前 BST 里还没数过的最小值，准备把它计入：count 将变成 2。
节点 2 数完了，count = 2（蓝色=已计数）。升序序列变成 1 < 2。还没到第 6 个，继续中序走下一个更大的数。
中序怎么找下一个？弹回栈顶的父节点（左子树已数完）。当前定位到节点 3（它是所有未数节点里最小的），下一步把它计入。
中序走到当前最小的未访问节点 = 3（橙色）。它是目前 BST 里还没数过的最小值，准备把它计入：count 将变成 3。
节点 3 数完了，count = 3（蓝色=已计数）。升序序列变成 1 < 2 < 3。还没到第 6 个，继续中序走下一个更大的数。
中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 4（它是所有未数节点里最小的），下一步把它计入。
中序走到当前最小的未访问节点 = 4（橙色）。它是目前 BST 里还没数过的最小值，准备把它计入：count 将变成 4。
节点 4 数完了，count = 4（蓝色=已计数）。升序序列变成 1 < 2 < 3 < 4。还没到第 6 个，继续中序走下一个更大的数。
中序怎么找下一个？弹回栈顶的父节点（左子树已数完）。当前定位到节点 5（它是所有未数节点里最小的），下一步把它计入。
中序走到当前最小的未访问节点 = 5（橙色）。它是目前 BST 里还没数过的最小值，准备把它计入：count 将变成 5。
节点 5 数完了，count = 5（蓝色=已计数）。升序序列变成 1 < 2 < 3 < 4 < 5。还没到第 6 个，继续中序走下一个更大的数。
中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 6（它是所有未数节点里最小的），下一步把它计入。
中序走到当前最小的未访问节点 = 6（橙色）。它是目前 BST 里还没数过的最小值，准备把它计入：count 将变成 6。
count 数到 6，正好等于 k = 6！当前节点 6（绿色）就是第 6 小的元素。后面的节点不用再看，直接返回 —— 这就是「提前停」。
只中序访问了 6 个节点（绿色=答案 6），剩下 8 个节点（7、8、9、10、11、12、13、14 这些更大的）根本没碰 —— 数到第 k 个立即返回，省掉后半棵树。
边界都落在中序序列的两端，想清楚就不会错。
两个高频追问：进阶维护子树大小、提前停的收益。
参考代码
def kthSmallest(root, k): stack = [] cur = root while stack or cur: while cur: # 一路向左 stack.append(cur) cur = cur.left cur = stack.pop() k -= 1 # 访问一个节点 if k == 0: return cur.val # 第 k 小，提前返回 cur = cur.right复杂度
- 时间：O(H + k)，先下到最左 O(H)，再访问 k 个节点
- 空间：O(H)，栈最多存一条从根到叶的路径，H 为树高
易错点
面试追问把动画讲成自己的话
追问如果树会频繁增删，且要反复查第 k 小，怎么优化？
追问为什么提前停能省时间？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从前序与中序遍历序列构造二叉树
LeetCode 105 · 中等 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题