230 二叉搜索树第k小的元素
中序遍历(直接版)
/**
* 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 {
private:
vector<int> ans;
void inOrder(TreeNode* root){
if(!root)
return;
inOrder(root->left);
ans.push_back(root->val);
inOrder(root->right);
}
public:
int kthSmallest(TreeNode* root, int k) {
inOrder(root);
return ans[k - 1];
}
};
中序遍历(优化版)
所谓优化就是不需要遍历整棵树,遍历过程中找到对应的节点就可以返回
递归
感觉用递归不太适合,这里就不贴出来了
迭代
/**
* 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) {
stack<TreeNode*> stk;
TreeNode* cur = root;
while(cur || !stk.empty()){
if(cur){
stk.push(cur);
cur = cur->left;
}else{
cur = stk.top();
stk.pop();
// 从k - 1开始计数
k--;
// 因此k == 0时对应第k个小的值
if(k == 0)
return cur->val;
cur = cur->right;
}
}
return 0;
}
};
复杂度分析
时间复杂度:O(H+k),其中 H 是树的高度。在开始遍历之前,我们需要 O(H) 到达叶结点。当树是平衡树时,时间复杂度取得最小值 O(logN+k);当树是线性树(树中每个结点都只有一个子结点或没有子结点)时,时间复杂度取得最大值 O(N+k)。
空间复杂度:O(H),栈中最多需要存储 H 个元素。当树是平衡树时,空间复杂度取得最小值 O(logN);当树是线性树时,空间复杂度取得最大值 O(N)
方法二:记录子树的结点数
如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第
k小的值,你将如何优化算法?
详见题解:
https://leetcode.cn/problems/kth-smallest-element-in-a-bst/solutions/1050055/er-cha-sou-suo-shu-zhong-di-kxiao-de-yua-8o07/?envType=study-plan-v2&envId=top-100-liked
/**
* 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 {
private:
unordered_map<TreeNode*,int> nodeNum;
int setNodeNum(TreeNode* node){
if(!node)
return 0;
int leftNum = setNodeNum(node->left);
int rightNum = setNodeNum(node->right);
nodeNum[node] = leftNum + rightNum + 1;
return nodeNum[node];
}
int getNodeNum(TreeNode* node){
if(node && nodeNum.count(node))
return nodeNum[node];
else
return 0;
}
public:
int kthSmallest(TreeNode* root, int k) {
if(!root)
return 0;
setNodeNum(root);
TreeNode* node = root;
while(node){
int leftNum = getNodeNum(node->left);
// 如果左子树节点树比 k - 1小,说明第k个数在右子树
// 此时左子树有 leftNum 个节点
// 也就是说此时我们已经找到了第k个节点左边的leftNum个节点
// 我们还需要填充k - 1 - leftNum个节点,就可以找到第k个节点
// 因此k = k - 1 - leftNum
if(leftNum < k - 1){
node = node->right;
k -= leftNum + 1;
}else if (leftNum == k - 1){
return node->val;
}else{
node = node->left;
}
}
return 0;
}
};
下一次寻找第k小的节点,只需要查找哈希表即可,为\(O(1)\)时间复杂度