友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
230. 二叉搜索树中第 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 <= 104 -
0 <= Node.val <= 104
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
思路分析
二叉搜索树的中根遍历是排好序的，所以，求第 K 最小值，直接中根遍历即可。
树的非递归遍历还需要多加推敲，加强理解。
-
一刷
-
二刷
-
三刷
-
四刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* Runtime: 1 ms, faster than 57.26% of Java online submissions for Kth Smallest Element in a BST.
*
* Memory Usage: 46.1 MB, less than 5.51% of Java online submissions for Kth Smallest Element in a BST.
*
* Copy from: https://leetcode.com/problems/kth-smallest-element-in-a-bst/solution/[Kth Smallest Element in a BST solution - LeetCode]
*/
public int kthSmallest(TreeNode root, int k) {
LinkedList<TreeNode> stack = new LinkedList<>();
while (true) {
while (Objects.nonNull(root)) {
stack.add(root);
root = root.left;
}
root = stack.removeLast();
if (--k == 0) {
return root.val;
}
root = root.right;
}
}
/**
* Runtime: 4 ms, faster than 8.53% of Java online submissions for Kth Smallest Element in a BST.
*
* Memory Usage: 49.7 MB, less than 5.51% of Java online submissions for Kth Smallest Element in a BST.
*/
public int kthSmallestRecursion(TreeNode root, int k) {
List<Integer> list = new ArrayList<>();
inorder(root, list);
return list.get(k - 1);
}
private void inorder(TreeNode root, List<Integer> list) {
if (Objects.nonNull(root.left)) {
inorder(root.left, list);
}
list.add(root.val);
if (Objects.nonNull(root.right)) {
inorder(root.right, list);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Morris 中序遍历
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-08 14:51:44
*/
public int kthSmallest(TreeNode root, int k) {
TreeNode cur = root;
TreeNode mostRight = null;
TreeNode result = null;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
}else {
mostRight.right = null;
}
}
k--;
if (k == 0) {
result = cur;
break;
}
System.out.println(cur.val);
cur = cur.right;
}
return result.val;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Morris 中序遍历
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-13 22:09:21
*/
public int kthSmallest(TreeNode root, int k) {
TreeNode curr = root;
while (curr != null) {
TreeNode mostRight = curr.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != curr) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = curr;
curr = curr.left;
continue;
} else {
mostRight.right = null;
}
}
k--;
if (k == 0) {
return curr.val;
}
curr = curr.right;
}
// 不会走到这里，加这句话只是保证编译不报错
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-10-24 18:08:06
*/
int k = 0;
public int kthSmallest(TreeNode root, int k) {
this.k = k;
return dfs(root);
}
private Integer dfs(TreeNode root) {
if (root == null) {
return null;
}
Integer left = dfs(root.left);
if (left != null) {
return left;
}
if (k == 1) {
return root.val;
} else {
k--;
}
Integer right = dfs(root.right);
if (right != null) {
return right;
}
return null;
}