title: 每日一练（26）：二叉搜寻树的第 k 大节点
categories:[剑指 offer]
tags:[每日一练]
date: 2022/02/25
每日一练（26）：二叉搜寻树的第 k 大节点
给定一棵二叉搜寻树，请找出其中第 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 ≤ 二叉搜寻树元素个数
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
办法一：vector 递归
class Solution {
public:
vector<int> ans;
void dfs(TreeNode* root) {if (!root) {return;}
dfs(root->left);
ans.push_back(root->val);
dfs(root->right);
}
int kthLargest(TreeNode* root, int k) {dfs(root);
return ans[ans.size() - k];
}
};办法二：变量递归
把本来是“左中右”的中序遍历改成“右中左”的反向中序遍历
保护两个变量 count 和 res 即可。count 用来计数咱们在降序的数字序列中走了几位，当走了 k 位时，就让 res 等于以后的 root -> val，而后退出 inorder 函数即可
class Solution {
public:
// 二叉搜寻树的中序遍历是递增序列
int count, res;
void dfs(TreeNode* root, int k){if (root == nullptr) {return;}
dfs(root->right, k);
count++;
if (count == k) {
res = root->val;
return;
}
dfs(root->left, k);
}
int kthLargest(TreeNode* root, int k) {dfs(root, k);
return res;
}
};