荷叶生时春恨生
荷叶枯时秋恨成
C++，二叉搜索树，递归。
这道题最简单的思路就是直接中序遍历，然后得到一个中序序列数组，直接从中序数组中得到第k小。题目当然可以做出来，但是面试的时候这么做恐怕不行，隐含条件应该就是不能额外申请空间。
不用数组记录怎么做呢？
答案：利用中序遍历的特性。
利用一个变量记录当前已经遍历的结点数目，如果已经遍历的结点数目已经等于k时，就说明这是第k小了呀。。。
简单吧！！！
代码如下：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k) {
if (!pRoot) return pRoot;
TreeNode *ans = nullptr;
inorder(pRoot, k, ans);
return ans;
}
void inorder(TreeNode* root, int &k, TreeNode *&ans) {
if (!root || ans) return ;
inorder(root->left, k, ans);
k--;
if (k == 0) ans = root;
inorder(root->right, k, ans);
}
};
