[Leetcode][230. 二叉搜索树中第K小的元素] 3种方法：
By Long Luo
Leetcode 230. 二叉搜索树中第K小的元素 题解。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18230. 二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点root，和一个整数$k$，请你设计一个算法查找其中第$k$个最小元素（从$1$开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
提示：
树中的节点数为 n 。
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第$k$小的值，你将如何优化算法？
方法一：中序遍历 + 递归
思路与算法：
二叉搜索树具有如下性质：
- 结点的左子树只包含小于当前结点的数。
- 结点的右子树只包含大于当前结点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
二叉树的中序遍历即按照访问左子树——根结点——右子树的方式遍历二叉树；在访问其左子树和右子树时，我们也按照同样的方式遍历；直到遍历完整棵树。
因为二叉搜索树和中序遍历的性质，所以二叉搜索树的中序遍历是按照键增加的顺序进行的。于是，我们可以通过中序遍历找到第\(k\)个最小元素。
代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public int kthSmallest(TreeNode root, int k) {
List<Integer> nums = new ArrayList<>();
inOrder(root, nums);
return nums.get(k - 1);
}
public void inOrder(TreeNode root, List<Integer> numberList) {
if (root == null) {
return;
}
inOrder(root.left, numberList);
numberList.add(root.val);
inOrder(root.right, numberList);
}
复杂度分析：
- 时间复杂度：\(O(N)\)，其中\(N\)是树的节点数。
- 空间复杂度：\(O(N)\)，需要额外存储每个节点的值。
方法二：中序遍历 + 迭代
思路与算法：
方法一使用的是递归来进行中序遍历，实际上，我们也可以使用迭代方法来进行中序遍历，如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> nums = new ArrayList<>();
while (root != null || !stack.empty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
nums.add(root.val);
root = root.right;
}
return nums.get(k - 1);
}
实际上，使用迭代方法，我们可以在找到答案后就停止，而不需要遍历整棵树，优化后的代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.empty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
k--;
if (k == 0) {
break;
}
root = root.right;
}
return root.val;
}
复杂度分析：
- 时间复杂度：\(O(H+k)\)，其中\(H\)是树的高度。在开始遍历之前，我们需要\(O(H)\)到达叶结点。当树是平衡树时，时间复杂度取得最小值\(O(\log N + k)\)；当树是线性树（树中每个结点都只有一个子结点或没有子结点）时，时间复杂度取得最大值\(O(N+k)\)。
- 空间复杂度：\(O(H)\)，栈中最多需要存储\(H\)个元素。当树是平衡树时，空间复杂度取得最小值\(O(\log N)\)；当树是线性树时，空间复杂度取得最大值\(O(N)\)。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗