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

题⽬描述

给定⼀棵⼆叉搜索树，请找出其中的第 k ⼩的 TreeNode 结点。
示例1
输⼊：{5,3,7,2,4,6,8},3
返回值：{4}
思路及解答

二叉搜索树的关键性质

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

算法思路：

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

1. class TreeNode {
2.     int val;
3.     TreeNode left;
4.     TreeNode right;
5.     TreeNode(int x) { val = x; }
6. }
8. public class Solution {
9.     public int kthSmallest(TreeNode root, int k) {
10.         // 用于存储中序遍历结果的列表
11.         List<Integer> inorderList = new ArrayList<>();
12.         // 执行中序遍历
13.         inorderTraversal(root, inorderList);
14.         // 返回第k小的元素（列表索引从0开始，所以是k-1）
15.         return inorderList.get(k - 1);
16.     }
17.    
18.     /**
19.      * 递归中序遍历二叉树
20.      * @param node 当前遍历的节点
21.      * @param list 存储遍历结果的列表
22.      */
23.     private void inorderTraversal(TreeNode node, List<Integer> list) {
24.         if (node == null) {
25.             return; // 递归终止条件：遇到空节点则返回
26.         }
27.         inorderTraversal(node.left, list);  // 递归遍历左子树
28.         list.add(node.val);                 // 访问当前节点，将值加入列表
29.         inorderTraversal(node.right, list); // 递归遍历右子树
30.     }
31. }

复制代码

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

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

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

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

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

复制代码

• 时间复杂度：最坏情况O(n)（当k=n时仍需遍历大部分节点），平均情况优于O(n)，因为可能提前返回。
  
• 空间复杂度：O(h)，其中h是树的高度。栈的深度最大为树高，在平衡BST中为O(log n)。
  

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

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

• 修改树节点结构，增加一个字段（如size）表示以该节点为根的子树的总节点数。
  
• 在插入、删除节点时，维护每个节点的size信息。
  
• 查询第k小的节点时：
  
  
  
  • 从根节点开始。
    
  • 计算左子树的节点数leftSize。
    
  • 如果k  leftSize + 1，说明目标节点在右子树，递归地在右子树中寻找第k - (leftSize + 1)小的节点。
    
  
  

[code]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

yyds。多谢分享

谢谢楼主提供！

感谢分享

新版吗？好像是停更了吧。

感谢，下载保存了

谢谢分享，辛苦了

喜欢鼓捣这些软件，现在用得少，谢谢分享！

很好很强大  我过来先占个楼 待编辑

用心讨论，共获提升！

这个好，看起来很实用

收藏一下   不知道什么时候能用到

感谢发布原创作品，程序园因你更精彩

感谢分享，学习下。

前排留名，哈哈哈