题目描述
给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
思路
二叉搜索树的中序遍历的输出结果是拍好序的，直接输出第K个即可
public class Solution {
int time = 0;
TreeNode KthNode(TreeNode root, int k){
if(root==null) return null;
TreeNode node = KthNode(root.left,k);
if(node!=null) return node;
time++;
if(time==k)
return root;
node = KthNode(root.right,k);
return node;
}
}
20180321
public class Solution {
int time = 0;
TreeNode res ;
TreeNode KthNode(TreeNode root, int k)
{
help(root,k);
return res;
}
private void help(TreeNode root,int k){
if(root==null)
return ;
help(root.left,k);
time++;
if(time ==k)
res = root;
help(root.right,k);
}
}
c++:20180731
/*
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* root, int k)
{
int cnt = ;
stack<TreeNode*> s ;
while(root!=NULL ||!s.empty()){
while(root!=NULL){
s.push(root);
root = root->left;
}
if(!s.empty()){
root = s.top();
s.pop();
cnt++;
if(cnt==k) return root;
root = root->right;
}
}
return NULL;
} };