- 题目描述
给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
- 题目解答
中序遍历二叉树，找到第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, unsigned int k)
{
if (pRoot == NULL || k == 0)
return NULL;
stack<TreeNode*> s;
int count = 0;
TreeNode* node = pRoot;
do{
if (node != NULL){
s.push(node);
node = node->left;
}
else{
node = s.top();
s.pop();
count++;
if (count == k)
return node;
node = node->right;
}
} while (node != NULL || !s.empty());//这里的条件要记牢
return NULL;
}
};