hot100 二叉搜索树中第 K 小的元素(230)
本题采用中序遍历递归剪枝算法（又称“计数状态递减拦截法”）解决二叉搜索树第 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 的状态值 | 触发的分支与状态判定 | 空间调用栈物理状态说明 |
| 初始 | 3 | 1 | 3 不为空且 k 大于 0，触发左递归 | 栈深: [3] |
| 1 | 1 | 1 | 1 不为空且 k 大于 0，触发左递归 | 栈深: [3, 1] |
| 2 | null (1的左孩子) | 1 | 触发 root == null，直接返回 | 栈深: [3, 1, null] -> 弹出 |
| 3 | 1 | 1 -> 0 | 执行 k-- 变为 0，判定 k == 0 成立，锁定 ans = 1 | 栈深: [3, 1] |
| 4 | 1 | 0 | 触发右递归，传入 1 的右孩子 2 | 栈深: [3, 1] |
| 5 | 2 | 0 | 满足 k <= 0 拦截条件，不执行任何子树访问，直接返回 | 栈深: [3, 1, 2] -> 弹出 |
| 6 | 1 | 0 | 1 的右递归返回，1 节点处理完毕 | 栈深: [3, 1] -> 弹出 |
| 7 | 3 | 0 | 回溯到根节点 3，执行 k-- 使得 k 变为 -1 | 栈深: [3] |
| 8 | 3 | -1 | 触发右递归，传入 3 的右孩子 4 | 栈深: [3] |
| 9 | 4 | -1 | 满足 k <= 0 拦截条件，不执行任何子树访问，直接返回 | 栈深: [3, 4] -> 弹出 |
| 10 | 3 | -1 | 3 的右递归返回，全局构建与搜索完毕 | 栈深: [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)，空间消耗的本质是拓扑树高的函数。