题目地址：

https://www.acwing.com/problem/content/66/

给定一棵二叉搜索树，请找出其中的第$k$小的结点。你可以假设树和$k$都存在，并且$1\le k\le n$，$n$为树的总结点数。

数据范围：
树中节点数量$[1,500]$。

中序遍历即可。代码如下：

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};class Solution {
public:TreeNode* kthNode(TreeNode* root, int k) {return dfs(root, k);}TreeNode* dfs(TreeNode* x, int& k) {if (!x) return nullptr;TreeNode* l = dfs(x->left, k);if (l) return l;if (!--k) return x;return dfs(x->right, k);}
};

时间复杂度$O(n)$，空间$O(h)$。