给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。
/*
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)
{
TreeNode* res = NULL;
if (pRoot == NULL || k <= ){
return res;
}
int count = ;
return InOrderTraverse(pRoot, k, count); //注意引用的时候必须是变量
} TreeNode* InOrderTraverse(TreeNode* pRoot, int k,int& count){
TreeNode* res = NULL;
if (pRoot->left != NULL){
res = InOrderTraverse(pRoot->left, k, count);
} if (res == NULL){ // 每一个结点的时候都要区判断是否已经查找到目标结点,这里用res不为空代表已经找到目标结点
count++; // count 用来标识 每次遍历一个结点,就会加1,若等于K就说明找到目标结点
if (count == k){
res = pRoot;
}
} if (pRoot->right != NULL && res == NULL){ //当右子树不为空 并且 还没有找到目标结点的时候才会遍历右子树
res = InOrderTraverse(pRoot->right, k, count);
}
return res;
}
};