题型地图 56天全屏 141题

当前：LC230 · 二叉搜索树中第 K 小的元素 · 首次出现于 Day 19 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

89 / 141回到 Day 19 卡片 141 题索引

BST中序遍历显式栈第 K 小

LC230 二叉搜索树中第 K 小的元素

利用 BST 的中序遍历天然升序，数到第 k 个就是答案

本页先讲清楚

BST 为什么自带大小关系

中序遍历为什么等于升序

显式栈如何模拟递归

为什么显式栈空间是 O(h)

original problem

原题区

给定一个二叉搜索树 root 和一个整数 k，请你设计一个算法，找出其中第 k 小的元素。

root = [5,3,6,2,4,null,null,1]

k = 3

输出：3

plain language

题意翻译区

这题不是让我们排序数组，而是让我们在一棵二叉搜索树里找第 k 小的节点。关键是 BST 本身已经隐含了大小关系。

bst primer

BST 概念预讲区

1. 左子树所有节点都比当前节点小。
2. 右子树所有节点都比当前节点大。
3. 所以按“左 → 根 → 右”访问，会得到升序序列。

core idea

为什么中序遍历能找到第 k 小？

中序遍历顺序是：左子树 → 当前节点 → 右子树。

对于 BST 来说，左边更小，当前居中，右边更大。

所以中序遍历结果就是从小到大的序列。

中序序列：[1, 2, 3, 4, 5, 6]

k = 3

答案 = 3

execution lab

动画实验室

执行实验室同时盯住四件事：BST 树、Go 代码高亮、stack 栈面板、k 倒计时和 visited 访问序列。

命中时：节点 3 高亮，右侧显示“k = 0，返回 3”

1/10 · k = 3

当前字幕

Step 1：cur 指向 5，说明从根节点开始。

当前发生了什么：cur 指向根节点 5，stack 还是空的。

为什么这么做：树的入口只有 root，迭代版先用 cur 表示“现在走到哪里”。

机器状态：cur=5，stack=[]，k=3，visited=[]

当前结论：还没有访问任何节点，k 仍然是 3。

左侧：BST 树

cur = 5

琥珀：在 stack 里

绿色：已访问

中间：Go 代码高亮

1func kthSmallest(root *TreeNode, k int) int {

2 stack := []*TreeNode{}

3 cur := root

5 for cur != nil || len(stack) > 0 {

6 for cur != nil {

7 stack = append(stack, cur)

8 cur = cur.Left

9 }

11 cur = stack[len(stack)-1]

12 stack = stack[:len(stack)-1]

14 k--

15 if k == 0 {

16 return cur.Val

17 }

19 cur = cur.Right

20 }

22 return -1

23}

右侧：stack / k / visited

k = 3

stack 栈面板栈顶在上

空栈

k 倒计时

visited 访问序列

[]

机器状态：cur / stack / k / visited

cur=5 · stack=[] · k=3 · visited=[]

go code

Go 代码区

1. 递归中序版

func kthSmallestRecursive(root *TreeNode, k int) int {
    count := 0
    ans := -1

    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil || ans != -1 {
            return
        }

        dfs(node.Left)

        count++
        if count == k {
            ans = node.Val
            return
        }

        dfs(node.Right)
    }

    dfs(root)
    return ans
}

2. 显式栈迭代版

重点展示这个版本，因为它和动画一致。

func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    cur := root

    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }

        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        k--
        if k == 0 {
            return cur.Val
        }

        cur = cur.Right
    }

    return -1
}

外层 for

只要 cur 还指着节点，或者 stack 里还有没访问的祖先，就说明还有节点没处理。

内层 for

一路向左，先找更小的节点；沿途把父节点压入 stack，等左边走完再回来。

pop

左边走到底后，当前弹出的就是还没访问过的最小节点。

k--

每访问一个节点，就消耗一个排名。k 从 3、2、1 往下倒数。

k == 0

当 k 被消耗到 0，当前节点就是第 k 小，立刻返回，不必遍历整棵树。

complexity

复杂度区

递归版

时间 O(k) 平均，最坏 O(n)

空间 O(h)

显式栈版

时间 O(k) 平均，最坏 O(n)

空间 O(h)

h 是树高。平衡树 h = log n，极端退化链表 h = n。不要写显式栈 O(1)，显式栈不是 O(1) 空间；只有 Morris 遍历才是 O(1) 额外空间。

interview answer

面试回答模板

这题利用 BST 的性质：左子树小于根，右子树大于根。所以 BST 的中序遍历结果是升序的。我们可以中序遍历整棵树，并在访问节点时计数，当计数到 k 时，当前节点就是第 k 小。实现上可以用递归，也可以用显式栈模拟递归。时间复杂度平均 O(k)，最坏 O(n)，空间复杂度 O(h)。

common mistakes

常见误区

误区 1

把 k 当成从 0 开始，其实第 k 小通常从 1 开始数。

误区 2

忘记 BST 的中序遍历才是有序，普通二叉树不行。

误区 3

显式栈不是 O(1) 空间。

误区 4

访问顺序写成根 → 左 → 右，会变成前序遍历，不是升序。

误区 5

没有提前停止，虽然能过，但不够优雅。