题目
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
1
2
3
4
5
6
7
|
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
|
示例 2:
1
2
3
4
5
6
7
8
9
|
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3
|
进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
题解
二叉搜索树的特征是每个节点的左子树的所有元素都小于该节点值，而右子树的所有元素都大于该节点值。基于该特征，中序遍历得到的值便是从小到大排列的，我们对整棵树进行中序遍历即可。
相应的实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
bool dfs(TreeNode* root, int &k, int &val) {
if (!root) return false;
if (dfs(root->left, k, val))return true;
if (--k == 0) {
val = root->val;
return true;
}
if (dfs(root->right, k, val))return true;
return false;
}
int kthSmallest(TreeNode* root, int k) {
int val = 0;
dfs(root, k, val);
return val;
}
|
在dfs函数中，我们加上了bool返回值，以便在找到结果后迅速返回，避免遍历整棵树，节省时间。