1吻氧、題目描述
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.
Example 1:
Input: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
Output: 1
Example 2:
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?
2麻献、問題描述：
- 二叉搜索樹的遍歷，求第k個結(jié)點的值。
3熙卡、問題關鍵：
- 二叉樹的中序遍歷芍锦，是從小到達排列的，所以裹虫，只需要中序遍歷到第k個就可以了肿嘲。
- 中序遍歷，第k個筑公，如果在根結(jié)點的左邊雳窟，那么k <= 0; 如果左子樹遍歷完了k=1，那么就是返回root的值匣屡，否則遍歷右子樹封救。
4、C++代碼：
class Solution {
public:
int dfs(TreeNode* root, int &k) {
if (!root) return 0;
int left = dfs(root->left, k);//遍歷左子樹
if (k <= 0) return left;//如果左子樹存在捣作，那么返回左子樹的值誉结。
if (--k == 0) return root->val;//如果遍歷左子樹
return dfs(root->right, k);
}
int kthSmallest(TreeNode* root, int k) {
return dfs(root, k);
}
};
