【LeetCode 230】算法：二叉搜索树中第 K 小的元素

题目：给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

算法设计：
在二叉搜索树（BST）中，中序遍历可以按照从小到大的顺序访问所有节点。因此，要找到第 k 小的元素，可以通过中序遍历来实现。
中序遍历法：

• 使用递归或栈实现中序遍历。
  
• 在遍历过程中，记录已经访问的节点数量。
  
• 当访问到第 k 个节点时，返回该节点的值。
  

优化方案：
如果需要多次查询第 k 小的元素，可以使用一个数组来存储中序遍历的结果，然后直接通过索引访问。这样可以将多次查询的时间复杂度降低到 O(1)。
一、递归法
复杂度：

• 时间复杂度：O(n)，其中 n 是树中节点的数量。最坏情况下需要遍历所有节点。
  
• 空间复杂度：O(h)，其中 h 是树的高度。这是因为递归调用栈的深度最多为树的高度。
  

Java 代码实现：

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {}
8. *     TreeNode(int val) { this.val = val; }
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
18.     int count = 0;  // 记录当前访问的节点数量
19.     int res;        // 存储第 k 小的元素
21.     public int kthSmallest(TreeNode root, int k) {
22.         if(root==null)  return -1;
23.         // 中序遍历
24.         inOrderTraversal(root, k);
25.         return res;
26.     }
28.     private void inOrderTraversal(TreeNode node, int k){
29.         // 递归出口
30.         if(node == null)  return;
31.         // 1.遍历左子树
32.         inOrderTraversal(node.left, k);
33.         // 2.先遍历完左子树，再访问当前结点
34.         count++;
35.         if(count == k){
36.             res = node.val;
37.             return;
38.         }
39.         // 3.遍历右子树
40.         inOrderTraversal(node.right, k);
41.     }
42. }

复制代码

二、迭代法
复杂度：

• 时间复杂度：O(n)，因为每个节点最多被访问两次（一次入栈，一次出栈）。
  
• 空间复杂度：O(h)，因为栈的深度最多为树的高度 h。
  

Java 代码实现：

1. class Solution {
2.     public int kthSmallest(TreeNode root, int k) {
3.         Stack<TreeNode> stack = new Stack<>();
4.         TreeNode current = root;
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--;
15.             if (k == 0) {
16.                 return current.val;
17.             }
18.             // 转向右子树
19.             current = current.right;
20.         }
21.         return -1; // 如果没有找到，返回一个错误值
22.     }
23. }

复制代码

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除