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

中等通过率 79.8%python3核心代码模式二叉树样例通过牛客 AC树深度优先搜索二叉搜索树二叉树

牛客原题　源码

讲解章节：树的基础与遍历

一句话

中序遍历天然升序，数到第 k 个就收工。

解题思路¶

这题考什么¶

BST（二叉搜索树）的中序遍历（左 -> 根 -> 右）恰好是节点值的升序序列。这条性质把「找第 k 小」直接化成「把中序序列数到第 k 个」，既不用排序，也不用把所有值都取出来再挑。

实现是标准的迭代中序：cur 一路沿 left 下钻并压栈，走到头就弹出栈顶（它的左子树已经全部处理完，轮到它自己），计数加一；计数到 k 时立刻返回，剩下的节点根本不用碰。中序的迭代模板见树的基础与遍历的「二叉树的三种遍历」一节。

示例 2：root = [5,3,6,2,4,null,null,1]，k = 3。

中序序列是 1, 2, 3, 4, 5, 6
数到第 3 个是 3，此时 4、5、6 还没被访问，直接返回 3，与样例一致。

数据规模与复杂度¶

1 <= k <= n <= 10^4，节点值在 [0, 10^4]。最坏（k = n）时每个节点入栈出栈各一次，时间 O(n)；一般情况只走到第 k 个就停，时间 O(h + k)，h 为树高。空间 O(h)，链状树退化到 O(n)。

坑在哪¶

必须迭代。n 到 1e4，而 BST 完全可以是一条链（按升序逐个插入建出来的就是），递归深度就是 1e4，远超 CPython 默认的 1000 层上限，递归中序会 RecursionError；递归改迭代见 DFS 深度优先搜索的 60.4 节。
k 从 1 开始计数。这里是「先加一再比较」，弹出第一个节点时 count 就是 1。写成「先比较再加一」，或者拿从 0 起算的计数去比 k，答案会整体偏一位。
提前退出是合法的，也是这题的重点。中序序列已经有序，第 k 个一旦到手，后面的值只会更大，继续遍历纯属浪费。
外层循环条件「cur 非空或栈非空」两个都要。只写 while stack 一开始栈是空的，循环进不去；只写 while cur 则弹出叶子后 cur 变成 None，还压在栈里的祖先再没机会被访问。
题面保证 k <= n，所以循环里一定会命中那次 return。函数末尾的 return -1 只是给「树里凑不够 k 个节点」的越界输入兜底 —— 节点值的下界是 0，-1 是个不可能出现的答案，一眼能看出是异常出口。

参考实现¶

solutions/leetcode/LC230/sol.py
from typing import List, Optional


class Solution:
    def kthSmallest(self, root: "Optional[TreeNode]", k: int) -> int:
        # 栈里是「左子树还没处理完」的祖先链
        stack: List["TreeNode"] = []
        cur = root
        # 已经确定名次的节点个数，也就是「当前弹出的是第几小」
        count = 0
        # 两个条件缺一不可：cur 非空是起步与刚转向右子树的状态，
        # cur 为空而栈非空是「左边走到头、该回头访问祖先」的状态
        while cur is not None or stack:
            # 一路向左下钻，沿途节点先记在栈上，等左子树处理完再回来访问
            while cur is not None:
                stack.append(cur)
                cur = cur.left
            # 弹出的节点左子树已经全部访问完，它就是中序里的下一个，也是下一小
            node = stack.pop()
            count += 1
            # 名次从 1 起算，所以先加一再比；命中即返回，后面的值只会更大
            if count == k:
                return node.val
            cur = node.right
        # 题面保证 k <= n，正常数据走不到这里；-1 不在值域 [0, 10^4] 内，是异常出口
        return -1

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