剑指offer-62、⼆叉搜索树的第k个结点

题⽬描述

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

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

思路及解答

二叉搜索树的关键性质

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

递归中序遍历（直观版）

算法思路：

1. 进行递归中序遍历
2. 将遍历到的节点值依次加入一个列表。
3. 遍历完成后，列表中的元素就是升序排列的。
4. 从列表中取出第k-1个元素（索引从0开始）即为答案。

java

class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public int kthSmallest(TreeNode root, int k) { // 用于存储中序遍历结果的列表 List<Integer> inorderList = new ArrayList<>(); // 执行中序遍历 inorderTraversal(root, inorderList); // 返回第k小的元素（列表索引从0开始，所以是k-1） return inorderList.get(k - 1); } /** * 递归中序遍历二叉树 * @param node 当前遍历的节点 * @param list 存储遍历结果的列表 */ private void inorderTraversal(TreeNode node, List<Integer> list) { if (node == null) { return; // 递归终止条件：遇到空节点则返回 } inorderTraversal(node.left, list); // 递归遍历左子树 list.add(node.val); // 访问当前节点，将值加入列表 inorderTraversal(node.right, list); // 递归遍历右子树 } }

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

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

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

算法思路：

1. 使用一个栈来模拟递归过程。
2. 从根节点开始，将所有左子节点压入栈，直到最左边的节点。
3. 弹出栈顶元素，这将是当前最小的节点。
4. 每弹出一个节点，计数器k减1。当k减到0时，当前节点就是第k小的节点，直接返回。
5. 如果k不为0，则转向当前节点的右子树，重复步骤2-4。

java

public class Solution { public int kthSmallest(TreeNode root, int k) { Deque<TreeNode> stack = new LinkedList<>(); TreeNode current = root; while (current != null || !stack.isEmpty()) { // 将当前节点及其所有左子节点压入栈 while (current != null) { stack.push(current); current = current.left; } // 弹出栈顶节点，即当前最小的节点 current = stack.pop(); k--; // 计数器减1 // 如果k减到0，说明找到了第k小的节点 if (k == 0) { return current.val; } // 转向右子树 current = current.right; } // 如果k超出节点总数，返回-1（根据题目保证k有效，此情况可不处理） return -1; } }

• 时间复杂度：最坏情况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)小的节点。

java

class TreeNodeWithSize { int val; TreeNodeWithSize left; TreeNodeWithSize right; int size; // 以该节点为根的子树包含的节点总数 TreeNodeWithSize(int x) { val = x; size = 1; // 初始时只有自身 } // 假设插入操作会更新size，这里省略具体的树结构维护代码 } public class Solution { public int kthSmallest(TreeNodeWithSize root, int k) { if (root == null) { return -1; } // 计算左子树的节点数（如果左子树为空，则节点数为0） int leftSize = (root.left != null) ? root.left.size : 0; if (k <= leftSize) { // 第k小的节点在左子树 return kthSmallest(root.left, k); } else if (k == leftSize + 1) { // 当前节点就是第k小的节点 return root.val; } else { // 第k小的节点在右子树，在右子树中寻找第 (k - (leftSize + 1)) 小的节点 return kthSmallest(root.right, k - (leftSize + 1)); }