Task
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Example
1
2
3
4
5
6
7
|
Input: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
Output: 1
|
1
2
3
4
5
6
7
8
9
|
Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
Output: 3
|
Follow 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?
Constraints:
- The number of elements of the BST is between
1 to 10^4.
- You may assume
k is always valid, 1 ≤ k ≤ BST's total elements.
Solution
- BST的性质是左子树的所有节点一定小于根节点，右子树的所有节点一定大于根节点。要按大小顺序遍历则选择
中序遍历，即先看左子树再看根节点再看右子树。本质上是在BST上做DFS
用队列存储遍历结果
- 中序遍历时每经过一个节点就将其放进队列中，遍历完成后整个队列是升序存储，pop掉前k-1个就得到第k大的
- 也可用vector存储队列
时间复杂度：由于要遍历一次，故O(n)空间复杂度：用额外队列存储所有元素，故O(n)- 实现：
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
|
// Runtime: 32 ms, faster than 50.85% of C++ online submissions for Kth Smallest Element in a BST.
// Memory Usage: 24.2 MB, less than 6.67% of C++ online submissions for Kth Smallest Element in a BST.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
queue<int> q;
//dfs遍历，得到升序队列
dfs(root,q);
//去除前k-1个元素
for(int i=0;i<k-1;++i)
q.pop();
return q.front();
}
private:
void dfs(TreeNode *root,queue<int> &q){
//dfs的递归终点是空节点
if(!root) return;
dfs(root->left,q);
//每次看到一个节点就存进队列中
//由于是中序遍历，故这一操作在遍历左子树之后，遍历右子树之前
q.push(root->val);
dfs(root->right,q);
}
};
|
用计数取遍历结果
- 用纯递归实现中序遍历求第k大的节点：
- 首先走到最左边的节点，即最小节点
- 维护一个计数，其初始值为k，每看一个节点就计数递减，减到0时返回该节点值
时间复杂度：由于要遍历一次，而计数减为0时结束，故O(k)空间复杂度：取决于递归深度，最好是完全二叉树O(logn)，最差是链表O(n)- 实现：
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
|
// Runtime: 20 ms, faster than 95.47% of C++ online submissions for Kth Smallest Element in a BST.
// Memory Usage: 24.1 MB, less than 6.67% of C++ online submissions for Kth Smallest Element in a BST.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
//调用递归函数
return inorder(root,k);
}
private:
//递归中序遍历
int inorder(TreeNode *root,int &k){
//以下两行的含义是一直往左走直到root的左子节点为空，终止递归
if(!root) return -1;
int x=inorder(root->left,k);
//若此时k减到0则左子树中找到第k大的节点
if(k==0) return x;
//看到根节点，k继续减，若此时k减到0则根节点是第k大的节点
if(--k==0) return root->val;
//继续查找右子树
return inorder(root->right,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
|
// Runtime: 24 ms, faster than 86.06% of C++ online submissions for Kth Smallest Element in a BST.
// Memory Usage: 24 MB, less than 6.67% of C++ online submissions for Kth Smallest Element in a BST.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
//初始化计数成员变量
cnt=k;
inorder(root);
return res;
}
private:
//中序遍历时维护计数成员变量和结果成员变量的值
void inorder(TreeNode *root){
if(root->left) inorder(root->left);
//计数减为0时当前节点的值即为所求
if(--cnt==0){
res=root->val;
return;
}
if(root->right) inorder(root->right);
}
//两个成员变量维护计数和结果
int cnt=0;
int res=0;
};
|