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?
Hint:
- Try to utilize the property of a BST.
- What if you could modify the BST node's structure?
- The optimal runtime complexity is O(height of BST).
题目意思：
给定一棵二叉搜索树，找到第k小的元素
注意：
1、利用二叉搜索树的特性
2、修改二叉搜索树的节点结构
3、最优时间复杂度是0(树的高度)
解题思路：
方法一：
二叉搜索树的特性：其中序遍历是有序的。故中序遍历访问，访问第k个元素即可。
方法二：
利用分冶的方法。
- 统计根节点左子树的节点个数cnt
- 如果cnt+1 = k，则根节点即为第k个最小元素
- 如果cnt+1 > k，则第k个最小元素在左子树，root = root->left;
- 如果cnt+1 < k，则第k个最小元素在右子树，root = root->right;
- 重复第一步
源代码：
方法一：
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> nodeStack;
if(root == NULL) return -;
while(true){
while(root){
nodeStack.push(root);
root = root->left;
}
TreeNode* node = nodeStack.top(); nodeStack.pop();
if(k == ) return node->val;
else root = node->right,k--;
}
}
};
方法二：
class Solution {
public:
int calcNodeSize(TreeNode* root){
if( root == NULL) return ;
return + calcNodeSize(root->left) + calcNodeSize(root->right);
}
int kthSmallest(TreeNode* root, int k) {
if(root == NULL) return ;
int cnt = calcNodeSize(root->left);
if(k == cnt + ) return root->val;
else if( k < cnt + ) return kthSmallest(root->left,k);
else return kthSmallest(root->right, k-cnt-);
}
};