二叉搜索树中第 K 小的元素 图解题解
BST 里有一条天然的升序通道——顺着它数到第 k 个就行。
BST 中序遍历（左→根→右）天然输出升序，就像把一叠按大小散放的卡片从最小那张开始翻。用栈模拟：一路压左孩子到底，弹出时是第一小；弹出后转向它的右孩子继续压左；每弹一次计数加一，数到第 k 次就是答案，右边的节点根本不用碰。
这道题到底在问什么
- 输入
- BST 如图，k = 6
- 输出
- 6
最优解：一步一步想明白
- 3核心一句话：BST 中序 = 升序，数到第 k 个就是第 K 小，提前停。
- 4完整的 BST。中序遍历从最左下角开始，按「左子树 → 根 → 右子树」的顺序访问，每访问一个节点 count 加 1。
- 5中序怎么找下一个？从根一路向左压栈，走到最左下角。当前定位到节点 1（它是所有未数节点里最小的），下一步把它计入。
- 6中序走到当前最小的未访问节点 = 1（橙色）。它是目前 BST 里还没数过的最小值，准备把它计入：count 将变成 1。
- 7节点 1 数完了，count = 1（蓝色=已计数）。升序序列变成 1。还没到第 6 个，继续中序走下一个更大的数。
- 8中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 2（它是所有未数节点里最小的），下一步把它计入。
- 9中序走到当前最小的未访问节点 = 2（橙色）。它是目前 BST 里还没数过的最小值，准备把它计入：count 将变成 2。
- 10节点 2 数完了，count = 2（蓝色=已计数）。升序序列变成 1 < 2。还没到第 6 个，继续中序走下一个更大的数。
- 11中序怎么找下一个？弹回栈顶的父节点（左子树已数完）。当前定位到节点 3（它是所有未数节点里最小的），下一步把它计入。
- 12中序走到当前最小的未访问节点 = 3（橙色）。它是目前 BST 里还没数过的最小值，准备把它计入：count 将变成 3。
- 13节点 3 数完了，count = 3（蓝色=已计数）。升序序列变成 1 < 2 < 3。还没到第 6 个，继续中序走下一个更大的数。
- 14中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 4（它是所有未数节点里最小的），下一步把它计入。
- 15中序走到当前最小的未访问节点 = 4（橙色）。它是目前 BST 里还没数过的最小值，准备把它计入：count 将变成 4。
- 16节点 4 数完了，count = 4（蓝色=已计数）。升序序列变成 1 < 2 < 3 < 4。还没到第 6 个，继续中序走下一个更大的数。
- 17中序怎么找下一个？弹回栈顶的父节点（左子树已数完）。当前定位到节点 5（它是所有未数节点里最小的），下一步把它计入。
- 18中序走到当前最小的未访问节点 = 5（橙色）。它是目前 BST 里还没数过的最小值，准备把它计入：count 将变成 5。
- 19节点 5 数完了，count = 5（蓝色=已计数）。升序序列变成 1 < 2 < 3 < 4 < 5。还没到第 6 个，继续中序走下一个更大的数。
- 20中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 6（它是所有未数节点里最小的），下一步把它计入。
- 21中序走到当前最小的未访问节点 = 6（橙色）。它是目前 BST 里还没数过的最小值，准备把它计入：count 将变成 6。
- 22count 数到 6，正好等于 k = 6！当前节点 6（绿色）就是第 6 小的元素。后面的节点不用再看，直接返回 —— 这就是「提前停」。
- 23只中序访问了 6 个节点（绿色=答案 6），剩下 8 个节点（7、8、9、10、11、12、13、14 这些更大的）根本没碰 —— 数到第 k 个立即返回，省掉后半棵树。
⚠️ 容易写错的地方
✗ 错：先中序存进数组再取第 k 个
✓ 对：边中序边数，k 到 0 立即返回
存满整棵树是 O(n) 空间+时间，提前停才省
✗ 错：把「第 k 小」当成树的第 k 层 / 第 k 个插入
✓ 对：是升序里的第 k 个，即中序第 k 个
BST 中序才是升序，与层、插入顺序无关
✗ 错：用前序/后序遍历
✓ 对：必须中序（左→根→右）
只有中序遍历 BST 才得到升序序列
完整代码（Python / C++ / Java）
Python
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.rightC++
int kthSmallest(TreeNode* root, int k){
stack<TreeNode*> st;
TreeNode* cur = root;
while(!st.empty() || cur){
while(cur){ st.push(cur); cur = cur->left; }
cur = st.top(); st.pop();
if(--k == 0) return cur->val;
cur = cur->right;
}
return -1;
}Java
public int kthSmallest(TreeNode root, int k){
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while(!stack.isEmpty() || cur != null){
while(cur != null){ stack.push(cur); cur = cur.left; }
cur = stack.pop();
if(--k == 0) return cur.val;
cur = cur.right;
}
return -1;
}复杂度
时间
O(H + k)
先下到最左 O(H)，再访问 k 个节点
空间
O(H)
栈最多存一条从根到叶的路径，H 为树高
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉搜索树中第 K 小的元素 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果树会频繁增删，且要反复查第 k 小，怎么优化？+
给每个节点维护「左子树节点数」（子树大小）。查第 k 小时：若左子树大小 = L，k≤L 进左子树；k==L+1 当前即答案；否则进右子树并 k-=L+1。每次查询 O(H)，增删时顺路维护计数。
为什么提前停能省时间？+
中序只需访问到第 k 个节点就能确定答案，之后所有更大的节点都无需访问。k 较小时远快于遍历整棵树的 O(n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 二叉搜索树中第 K 小的元素 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。