给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3解题思路： 在二叉搜索树中，任意子节点都满足“左子节点<根节点<右子节点”的规则。因此二叉搜索树具有一个重要性质：二叉搜索树的中序遍历为递增序列。
也就是说，本题可被转化为求中序遍历的第k个节点。
为求第k个节点，需要实现以下三项工作：
递归遍历时计数，统计当前节点的序号。 递归到第k个节点时，应记录结果res。 记录结果后，后续的遍历即失去意义，应提前返回。 代码： 题目指出：
（二叉搜索树节点个数）；因此无需考虑k > N的情况。 若考虑，可以在中序遍历完成后判断k>0是否成立，若成立则说明k > N。
代码语言：javascript复制class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
this->k = k;
dfs(root);
return res;
}
private:
int res, k;
void dfs(TreeNode* root) {
if (root == nullptr) return;
dfs(root->left);
if (k == 0) return;
if (--k == 0) res = root->val;
dfs(root->right);
}
};复杂度分析： 时间复杂度 O(N) ：
当树退化为链表，即全部为左子节点时，无论 kkk 的值大小，递归深度都为 N，使用 O(N) 时间。 空间复杂度 O(N) ：
当树退化为链表时，系统使用O(N)大小的栈空间。
