当前位置：首页 > java >正文

二叉树题解——二叉搜索树中第 K 小的元素【LeetCode】使用外部变量ans记录答案

java 2025/7/6 11:41:13

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

由于中序遍历就是在从小到大遍历节点值，所以遍历到的第 k 个节点值就是答案。

一、算法逻辑（逐步通顺讲解每一步思路）

该题目要求在一棵 二叉搜索树（BST） 中找到第 k 小的元素。

我们知道 BST 的中序遍历（左→根→右）会生成一个升序序列，因此，只要对整棵树进行中序遍历，并记录遍历到的第 k 个节点的值，即可得到答案。

该算法的流程如下：

✅ 1️⃣ 定义辅助变量：

ans 用于记录第 k 小的元素；
k 是倒计时变量，每访问一个节点就减 1。

✅ 2️⃣ 定义中序遍历函数 dfs(node)：

遇到空节点时返回；
优先递归访问左子树；
每访问一个节点，就将 k -= 1；
如果此时 k == 0，说明当前节点就是第 k 小的元素，将其值赋给 ans；
然后递归右子树。

✅ 3️⃣ 使用 nonlocal 保证在递归过程中能修改外部变量 k 和 ans。

✅ 4️⃣ 当 k == 0 时，整个递归过程中都会提前跳出剩余分支，从而实现剪枝加速。

✅ 5️⃣ 遍历完成后，返回记录的 ans 即可。

二、核心点总结

该算法的核心在于：

利用 BST 的中序遍历特性，使节点值按升序访问，倒数计数直到第 k 个元素，即为结果。

✅ 利用了 BST 的有序性，不需要额外排序；
✅ 通过中序遍历直接按顺序找到第 k 个元素；
✅ 使用 k == 0 作为提前剪枝条件，节省时间；
✅ 用 nonlocal 管理共享变量，递归写法清晰优雅。

class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:ans = 0def dfs(node:Optional[TreeNode]) -> None:nonlocal k, ansif node is None or k == 0:return dfs(node.left)k -= 1if k == 0:ans = node.valdfs(node.right)dfs(root)return ans