Given a binary search tree, write a function kthSmallest
to find the kth smallest element in it.
Note: You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
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?
找出二叉搜索树上第k大的数。
通常我们可以遍历一下,然后得到一个排序好的容器,直接在这个容器上查询就可以了,
但是这题说可能会经常对树进行插入和删除操作,这使得排序结果会经常变化,所以我们用中序遍历来实现。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode* root, int &k, int &res)
{
if(!root) return ;
dfs(root->left, k, res);
k--;
if(!k)
{
res = root->val;
return ;
}
dfs(root->right, k, res);
}
int kthSmallest(TreeNode* root, int k) {
int res;
dfs(root, k, res);
return res;
}
};