给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4限制：
- 1 ≤ k ≤ 二叉搜索树元素个数
1、用数组记录结点值
因为是二叉搜索树，所以只要我们中序遍历就能得到其正序序列，所以我们可以用数组将结点值存储起来，最后返回其第 k 大的结点值即可~
class Solution {
public:
void FindNode(TreeNode* root, vector<int>& v)
{
if(root == nullptr)
return;
// 中序遍历
FindNode(root->left, v);
v.push_back(root->val); // 记录节点值
FindNode(root->right, v);
}
int kthLargest(TreeNode* root, int k) {
vector<int> v;
FindNode(root, v);
return v[v.size() - k]; // 返回第k大的值也就是正数第v.size()-k大的数
}
};2、改变遍历顺序
因为二叉搜索树的中序遍历为正序，也就是先 左 --> 中 --> 右，那么只要我们变成 右 --> 中 --> 左 就能做到得到其反序列，那么只要遍历期间依次将 k 减小，减到为 0 说明就是第 k 大的结点，直接返回即可！
class Solution {
public:
void FindNode(TreeNode* root, int& k, int& final)
{
if(root == nullptr || k == 0)
return;
// 先向右递归
FindNode(root->right, k, final);
// 每次递减k，第一次k为0则root->val就是第k大的结点，用final记录下来
if(--k == 0)
{
final = root->val;
return;
}
FindNode(root->left, k, final);
}
int kthLargest(TreeNode* root, int k) {
int final = 0;
FindNode(root, k, final);
return final;
}
};