问题描述：
解决方案：
首先拿到这个题，就会想，先遍历一遍二叉树，将节点的值存储在数组中，然后对数组进行降序排序，就可以取出第k大的数字了。
然后遍历二叉树，有前序，中序，后序遍历。
然后这里提前回顾一下，二叉树的特性，比根节点小的数字在根节点的左边，比跟节点大的数字在跟节点的右边。
所以：如果按照中序遍历，左根右的顺序，是可以得到一个有序的数组，从小到大排序。
这里先说明一下，前序，中序，后序遍历的代码。
//中序
vector<int> storeNum(TreeNode* root,vector<int>&res)
{
if(root!=NULL){
storeNum(root->left,res);
res.push_back(root->val);
storeNum(root->right,res);
}
return res;
}
//前序
vector<int> storeNum(TreeNode* root,vector<int>&res)
{
if(root!=NULL){
res.push_back(root->val);
storeNum(root->left,res);
storeNum(root->right,res);
}
return res;
}
//后序
vector<int> storeNum(TreeNode* root,vector<int>&res)
{
if(root!=NULL){
storeNum(root->left,res);
storeNum(root->right,res);
res.push_back(root->val);
}
return res;
}
然后本题的代码来了
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
//先将所有的节点，存储在一个数组中，然后从大到小排序，就可以取出第k大的节点了
public:
int kthLargest(TreeNode* root, int k) {
vector<int> res;
if(root==NULL){
return 0;
}
res=storeNum(root,res);
return res[res.size()-k];
}
//中序遍历
vector<int> storeNum(TreeNode* root,vector<int>&res)
{
if(root!=NULL){
storeNum(root->left,res);
res.push_back(root->val);
storeNum(root->right,res);
}
return res;
}
};
但是结果很忧虑
然后我看到了一个解法，右根左 遍历方法，逆着遍历中序。
那么得到的就是第k大的数值了
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int res;
int kthLargest(TreeNode* root, int k) {
findK(root,k);
return res;
}
void findK(TreeNode* root,int &k){//传引用，这里保证所有的findK都用一个k
if(root!=NULL){
findK(root->right,k);
k--;
if(!k){
res=root->val;
}
findK(root->left,k);
}
}
};