本题采用中序遍历递归剪枝算法又称“计数状态递减拦截法”解决二叉搜索树第 k 小元素的检索问题。其核心本质是将二叉搜索树在中序遍历下的全局有序性转化为自左向右、自底向上的计数状态推进利用计数器归零实现对目标数值的精准捕获与即时剪枝。当前提供的源码实现了在时间复杂度 O(h k)其中 h 为树的高度和额外空间复杂度 O(h) 条件下的高效定位最终走向是精准返回树中第 k 小的节点数值。一、 问题本质与数据模型对于给定的二叉搜索树BST其核心物理特性是中序遍历左 - 根 - 右访问节点的顺序完美对应了节点数值从低到高排列的严格递增序列。如果将查找第 k 小元素的问题看作是对有序序列的索引定位最朴素的策略是遍历全树并将所有节点存储到线性容器中但这会产生不必要的空间开销。为了破除空间冗余的困局算法引入了“计数递减与即时拦截模型”。通过维护一个全局可变计数器 k在标准的递归中序遍历中每当完成对左子树的探测回溯到当前节点时意味着发现了一个更小的元素计数器 k 相应执行减 1 操作。一旦计数器 k 缩减至 0说明当前访问的节点即为目标节点此时将其数值锁定并写入结果变量。同时后续的所有子树递归操作均会被提前拦截达成无意义计算的彻底物理消除。二、 算法演进对比在查找二叉搜索树第 k 小元素的场景中带剪枝的中序遍历算法在运行效率与内存控制上实现了高度优化解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷全序收集法O(n)O(n)完整中序遍历全树并将结果存入数组直接通过下标索引 k - 1 定位内存消耗与节点规模成正比无法处理超大规模数据或流式数据带剪枝的中序遍历当前解法O(h k)O(h)利用 BST 中序递增特性计数器归零即时拦截返回并终止后续遍历受制于树的拓扑结构若树极度倾斜调用栈深度退化为 O(n)迭代显式栈法O(h k)O(h)使用外部栈模拟中序遍历弹出第 k 个元素时直接跳出循环需要手动维护栈结构代码结构相对繁琐三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于dfs(root)函数内的递归压栈、全局计数器k的步进更新以及k 0的边界拦截其内部决策分支证明如下1. 退出与剪枝拦截分支if (root null || k 0)执行直接返回终止当前分支探测。物理意义包含两种拦截场景。若是root null说明触及虚拟空边界属于常规触底回溯若是k 0说明目标元素已经在之前的遍历路径中被成功捕获并锁定了答案后续所有的左、右子树调用均为多余的算力浪费必须强制物理拦截。2. 严格保序左探测dfs(root.left);执行优先向左子树深处压栈推进。数学证明根据 BST 定义左子树所有节点均严格小于当前根节点。要寻找从小到大排列的第 k 个元素必须确保更小的值被优先计数因此左探测必须作为第一顺位执行。3. 计数状态更新与命中判定k--; if (k 0) { ans root.val; }执行计数器自减并核验是否归零。数学证明中序遍历在执行完dfs(root.left)回溯到当前根节点时表明左子树中所有更小的元素已经完成了计步。当前根节点正是当前未访问元素中的最小值。将其计入步长k--后若k 0则在数学上完全等价于“当前节点是全局第 k 小的元素”触发结果捕获。4. 右探测延伸dfs(root.right);执行向当前节点的右子树推进。数学证明右子树节点值均严格大于当前根节点。当左子树及当前根节点处理完毕且计数器仍大于 0 时说明第 k 小的元素必然位于值域更大的右半区因此需要将搜索弹道转向右子树。四、 算法执行状态机步进示例以输入二叉搜索树root [3, 1, 4, null, 2],k 1为例规模 n 4展示计数器递减与提前剪枝的状态机上演进过程步骤当前访问节点值全局计数器 k 的状态值触发的分支与状态判定空间调用栈物理状态说明初始313 不为空且 k 大于 0触发左递归栈深: [3]1111 不为空且 k 大于 0触发左递归栈深: [3, 1]2null (1的左孩子)1触发 root null直接返回栈深: [3, 1, null] - 弹出311 - 0执行 k-- 变为 0判定 k 0 成立锁定 ans 1栈深: [3, 1]410触发右递归传入 1 的右孩子 2栈深: [3, 1]520满足 k 0 拦截条件不执行任何子树访问直接返回栈深: [3, 1, 2] - 弹出6101 的右递归返回1 节点处理完毕栈深: [3, 1] - 弹出730回溯到根节点 3执行 k-- 使得 k 变为 -1栈深: [3]83-1触发右递归传入 3 的右孩子 4栈深: [3]94-1满足 k 0 拦截条件不执行任何子树访问直接返回栈深: [3, 4] - 弹出103-13 的右递归返回全局构建与搜索完毕栈深: [3] - 弹出全盘流程终止五、 源码实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public int kthSmallest(TreeNode root, int k) { // 初始化全局计数器将其绑定至类成员变量空间 this.k k; // 启动深度优先搜索中序遍历 dfs(root); // 返回在遍历过程中被精准截获的物理答案 return ans; } private int ans; private int k; private void dfs(TreeNode root) { // 核心控制与剪枝边界若节点为空或者计数器已归零或转负说明答案已被捕获直接拦截返回 if (root null || k 0) { return; } // 步骤 1保序下推优先检索值域更小的左子树 dfs(root.left); // 步骤 2状态计步回溯至当前节点说明发现一个有效小值计数器自减 k--; // 状态判定若计数器恰好归零说明当前节点即为全局第 k 小的目标元素 if (k 0) { ans root.val; } // 步骤 3弹道转向在当前值及左子树均无法填满 k 的步长时深入右子树检索 dfs(root.right); } }六、 复杂度分析1. 时间复杂度O(h k)分析中序遍历从根节点出发首先需要沿最左侧路径一路下推到树中的绝对最小值节点此步的代价取决于树的高度 h。随后算法依序访问从小到大的前 k 个节点。由于引入了k 0的即时剪枝拦截在访问完第 k 个节点并锁定答案后后续所有的节点访问和遍历都会被常数阶操作拦截直接返回。结论时间复杂度为 O(h k)。在完全平衡二叉树中高度 h 为对数阶总时间接近 O(log n k)在最坏情况下树退化为单链表h 可达 n。2. 空间复杂度O(h)分析算法在运行中外部没有申请多余的集合对象其空间占用完全依赖于底层维护的深度优先搜索递归方法调用栈。递归栈的最大深度与二叉树的高度 h 保持严格的同步关系。结论最大额外空间开销表现为 O(h)空间消耗的本质是拓扑树高的函数。