给定一棵二叉搜索树, 请找出其中的第 k 小的结点. 例如, (5,3,7,2,4,6,8) 中, 按结点数值大小顺序第三小结点的值为 4.
C++:
- /*
- struct TreeNode {
- int val;
- struct TreeNode *left;
- struct TreeNode *right;
- TreeNode(int x) :
- val(x), left(NULL), right(NULL) {
- }
- };
- */
- class Solution {
- private:
- TreeNode* res = NULL ;
- int cnt = 0 ;
- public:
- TreeNode* KthNode(TreeNode* pRoot, int k)
- {
- inOrder(pRoot,k) ;
- return res ;
- }
- void inOrder(TreeNode* pRoot, int k){
- if (pRoot == NULL || cnt>= k)
- return ;
- inOrder(pRoot->left,k) ;
- cnt++ ;
- if (cnt == k)
- res = pRoot ;
- inOrder(pRoot->right,k) ;
- }
- };
来源: http://www.bubuko.com/infodetail-3002485.html