友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
230. Kth Smallest Element in a BST
Given a binary search tree, write a function kthSmallest to find the *k*th smallest element in it.
*Note: *
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.
Example 1:
Input: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
Output: 1Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
Output: 3Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
思路分析
二叉搜索树的中根遍历是排好序的，所以，求第 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;
}