LeetCode-Go 题解 | 0230. Kth Smallest Element in a BST利用中序遍历求解二叉搜索树第 K 小元素【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文是 LeetCode-Go 仓库中 0230. Kth Smallest Element in a BST 一题的深度解析。题目要求在一个二叉搜索树BST中找出第 k 小的元素核心思路是利用 BST「中序遍历结果天然有序」这一性质在遍历到第 k 个节点时立即得到答案。读完本文你将掌握基于中序遍历计数的 Go 递归实现、其复杂度边界与提前终止细节并了解面对 Follow up频繁增删 频繁查询时如何通过为节点维护子树规模把单次查询优化到 O(log n)。题目要求给定一棵二叉搜索树请实现函数kthSmallest返回其中第k小的元素值。约束条件可以假设 k 总是有效的即1 ≤ k ≤ BST 的节点总数。示例 1Input: root [3,1,4,null,2], k 1 3 / \ 1 4 \ 2 Output: 1示例 2Input: root [5,3,6,2,4,null,null,1], k 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3Follow up如果这棵 BST 会被频繁修改插入 / 删除节点同时你又需要频繁查询第 k 小的元素如何优化kthSmallest例程二叉搜索树的核心性质与考点本题之所以能用极简的代码解决完全依赖于二叉搜索树BST的有序性对任意节点其左子树中的所有节点值都小于该节点其右子树中的所有节点值都大于该节点对左右子树递归地满足同样性质。由此可以推导出关键结论对 BST 进行中序遍历Inorder左 → 根 → 右得到的结果是一个严格递增的有序序列。因此第 k 小的元素就是中序遍历序列中的第 k 个元素。原文档的解题思路正是这一条由于二叉搜索树有序的特性所以中根遍历它遍历到第 K 个数的时候就是结果。仓库中的 structures/TreeNode.go 定义了统一的节点结构本题解直接复用它type TreeNode struct { Val int Left *TreeNode Right *TreeNode }解题思路中序遍历 计数整体思路分为三步从根节点出发对 BST 进行中序遍历维护一个计数器count每「访问」一个节点即把该节点当作当前根处理时计数加一当count k时当前节点的值就是第 k 小的元素记录结果并返回。由于中序遍历保证节点按值从小到大被访问第 k 次访问到的节点必然携带第 k 小的值正确性由 BST 性质直接保证。Go 源码实现详解仓库中的实现位于 230. Kth Smallest Element in a BST.go完整源码如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func kthSmallest(root *TreeNode, k int) int { res, count : 0, 0 inorder230(root, k, count, res) return res } func inorder230(node *TreeNode, k int, count *int, ans *int) { if node ! nil { inorder230(node.Left, k, count, ans) *count if *count k { *ans node.Val return } inorder230(node.Right, k, count, ans) } }下面对实现细节逐点拆解1. 类型别名复用仓库公共结构type TreeNode structures.TreeNode是类型别名type alias而非新类型定义。这意味着题解直接使用structures包中统一的二叉树节点可以与仓库中 Ints2TreeNode按层序切片建树、Tree2Inorder等工具函数无缝配合也是整个 LeetCode-Go 仓库「一套结构体、处处复用」的体现。2. 入口函数kthSmallest先声明结果变量res与计数器count然后调用inorder230开始递归。这里的关键设计是count与res都以指针形式传入递归函数。为什么必须用指针Go 语言中函数参数是值传递递归的每一层都会复制参数副本。如果直接传int内层递归对count的修改不会反映到外层计数就无法跨递归层级累积。用*int共享同一块内存才能保证「每个节点的访问计数」被全局累加。这是该实现中最值得注意的 Go 语言细节。3. 递归核心inorder230先递归左子树inorder230(node.Left, k, count, ans)——这保证了按从小到大顺序访问访问当前节点*count后判断*count k命中则把node.Val写入*ans并return未命中则继续递归右子树inorder230(node.Right, k, count, ans)。4. 提前终止的实际效果源码级观察从代码结构可以观察到一个值得注意的细节当*count k时当前节点的右子树被return直接跳过第 k 小的节点不可能出现在它自身右子树中因为那部分都更大这构成了一层剪枝但祖先节点的递归帧并不会全部退出——父节点恢复执行后仍会继续*count并遍历其右子树。因此最坏情况下例如k n要找最大元素函数仍会访问整棵树的所有节点整体时间复杂度仍为 O(n)。如果你想做到严格意义上的「找到即全停」可以额外引入一个终止标志位但本仓库的实现以简洁为先。复杂度分析时间复杂度O(n)其中 n 为节点总数。最坏情况如k n需要遍历整棵树平均场景下由于命中第 k 个节点后会跳过该节点的右子树实际访问节点数通常少于 n。空间复杂度O(H)H 为树的高度。递归调用栈深度等于当前遍历路径的长度最坏情况下退化为链状树为 O(n)平衡二叉树下为 O(log n)。测试用例与运行验证仓库为本题配套了完整的表驱动测试 230. Kth Smallest Element in a BST_test.go覆盖了三组输入qs : []question230{ { para230{[]int{}, 0}, ans230{0}, }, { para230{[]int{3, 1, 4, structures.NULL, 2}, 1}, ans230{1}, }, { para230{[]int{5, 3, 6, 2, 4, structures.NULL, structures.NULL, 1}, 3}, ans230{3}, }, }三组用例分别对应空树返回零值、示例 1k 1输出 1、示例 2k 3输出 3。测试通过 structures.Ints2TreeNode 将 LeetCode 风格的层序数组还原为真正的二叉树数组中的structures.NULL定义见 structures/TreeNode.go值为-1 63即最小的 int 值代表空节点占位Ints2TreeNode借助队列按层序遍历顺序逐层构造节点遇到NULL则跳过子节点连接与 LeetCode 平台的数组表示完全对齐。在本仓库中运行该题测试只需在项目根目录执行go test -v ./leetcode/0230.Kth-Smallest-Element-in-a-BST/仓库根目录的 gotest.sh 展示了全量测试与覆盖率采集的标准做法go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...生成的 coverage.txt 记录了仓库「100% 测试覆盖」的验证结果本题同样包含其中。Follow up频繁增删 频繁查询的优化方向原文档抛出了一个进阶问题如果 BST 被频繁修改insert/delete且需要频繁调用kthSmallest如何优化朴素中序遍历每次查询都要付出 O(n) 的代价在「写多读多」的场景下不可接受。经典优化方案是为节点增加「左子树规模」字段或整棵子树规模字段每个节点额外记录LeftSize其左子树的节点个数插入 / 删除时沿路径更新即可代价仍是 O(log n)平衡树场景查询第 k 小时从根节点出发若k node.LeftSize 1当前节点就是第 k 小若k node.LeftSize答案在左子树向左递归否则k - node.LeftSize 1向右子树递归。这样单次查询的代价与树高成正比在平衡 BST 下为 O(log n)。以下是一段示意实现非仓库既有代码仅用于呈现该优化思路// 带左子树规模的增强节点思路示意 type AugTreeNode struct { Val int Left *AugTreeNode Right *AugTreeNode LeftSize int // 左子树节点总数 } func kthSmallestAug(root *AugTreeNode, k int) int { if root nil { return 0 } if k root.LeftSize1 { return root.Val } if k root.LeftSize { return kthSmallestAug(root.Left, k) } return kthSmallestAug(root.Right, k-root.LeftSize-1) }需要注意这一方案的前提是「树的形态足够平衡」如果 BST 退化为链表无论是否增强字段查询都会退化回 O(n)。这也是为什么工程上常配合 AVL / 红黑树等自平衡结构使用。小结与相关文件索引本题的解法之所以能成为经典在于它把「BST 有序」与「中序遍历」两个知识点合二为一一条递归遍历、一个计数器即可在线性时间内回答第 k 小查询。仓库实现用指针传参完成跨层计数、命中即剪枝代码量虽少却包含了 Go 递归与树遍历的多个关键细节。深入阅读与本主题直接相关的仓库文件题目文档原题描述、示例与 Follow up题解源码kthSmallest与inorder230的完整实现测试用例表驱动测试与数组建树示例structures/TreeNode.go统一的TreeNode结构、NULL常量与Ints2TreeNode建树工具gotest.sh 与 coverage.txt全量测试与覆盖率验证脚本及结果【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考