题目描述 给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
#include <iostream>
using namespace std;
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
class Solution {
private:
int cnt;
TreeNode* ans;
public:
void Inorder(TreeNode* root){
if(cnt == 0){
return;
}
if(!root){
return;
}
this->Inorder(root->left);
cnt--;
if(cnt != 0){
ans = root;
}
this->Inorder(root->right);
}
TreeNode* KthNode(TreeNode* pRoot, int k){
if(!pRoot || k < 1){
return NULL;
}
cnt = k;
ans = NULL;
this->Inorder(pRoot);
return ans;
}
};