题⽬描述

给定⼀棵⼆叉搜索树，请找出其中的第 k ⼩的 TreeNode 结点。

示例1 输⼊：{5,3,7,2,4,6,8},3 返回值：{4}

思路及解答

二叉搜索树的关键性质

二叉搜索树具有一个重要特性：中序遍历（左-根-右）BST会得到一个升序排列的节点值序列。因此，寻找第k小的节点本质上就是获取中序遍历序列中的第k个元素。理解这一点是掌握所有解法的基石。

递归中序遍历（直观版）

算法思路：

  1. 进行递归中序遍历

  2. 将遍历到的节点值依次加入一个列表。

  3. 遍历完成后，列表中的元素就是升序排列的。

  4. 从列表中取出第k-1个元素（索引从0开始）即为答案。

  • 时间复杂度：O(n)。需要遍历树中的所有n个节点。

  • 空间复杂度：O(n)。主要取决于递归调用栈的深度（最坏情况为O(n)，树退化成链表）和存储遍历结果的列表（O(n)）。

迭代中序遍历（提前终止）

方法一需要遍历完整棵树，即使答案在很早就已确定。我们可以利用迭代中序遍历实现提前终止，找到第k小的节点后立即返回，提升效率。

算法思路：

  1. 使用一个栈来模拟递归过程。

  2. 从根节点开始，将所有左子节点压入栈，直到最左边的节点。

  3. 弹出栈顶元素，这将是当前最小的节点。

  4. 每弹出一个节点，计数器k减1。当k减到0时，当前节点就是第k小的节点，直接返回。

  5. 如果k不为0，则转向当前节点的右子树，重复步骤2-4。

  • 时间复杂度：最坏情况O(n)（当k=n时仍需遍历大部分节点），平均情况优于O(n)，因为可能提前返回。

  • 空间复杂度：O(h)，其中h是树的高度。栈的深度最大为树高，在平衡BST中为O(log n)。

记录子节点数的递归（进阶优化）

如果BST结构频繁变动（插入、删除），但需要频繁查询第k小的值，前两种方法每次查询都可能需要O(n)时间。我们可以通过扩展树节点结构，记录以每个节点为根的子树中的节点个数，来优化查询效率。

算法思路：

  1. 修改树节点结构，增加一个字段（如size）表示以该节点为根的子树的总节点数。

  2. 在插入、删除节点时，维护每个节点的size信息。

  3. 查询第k小的节点时：

  • 从根节点开始。

  • 计算左子树的节点数leftSize。

  • 如果k <= leftSize，说明目标节点在左子树，递归地在左子树中寻找第k小的节点。

  • 如果k == leftSize + 1，说明当前根节点就是目标节点。

  • 如果k > leftSize + 1，说明目标节点在右子树，递归地在右子树中寻找第k - (leftSize + 1)小的节点。