題目來源
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:
int kthSmallest(TreeNode* root, int k) {
int count = 0, res = 0;
helper(root, k, res);
return res;
}
void helper(TreeNode* node, int &k, int &res)
{
if (node->left != NULL)
helper(node->left, k, res);
k--;
if (k == 0) {
res = node->val;
return;
}
if (node->right != NULL)
helper(node->right, k, res);
}
};
