给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。

 

C++:

1 /* 2 struct TreeNode { 3     int val; 4     struct TreeNode *left; 5     struct TreeNode *right; 6     TreeNode(int x) : 7             val(x), left(NULL), right(NULL) { 8     } 9 };10 */11 class Solution {12 private:13     TreeNode* res = NULL ;14     int cnt = 0 ;15 public:16     TreeNode* KthNode(TreeNode* pRoot, int k)17     {18         inOrder(pRoot,k) ;19         return res ;20     }21     22     void inOrder(TreeNode* pRoot, int k){23         if (pRoot == NULL || cnt >= k)24             return ;25         inOrder(pRoot->left,k) ;26         cnt++ ;27         if (cnt == k)28             res = pRoot ;29         inOrder(pRoot->right,k) ;30     }31 32     33 };