二叉搜索树的第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 ≤ 二叉搜索树元素个数
解法：
右孩子、父节点、左孩子，按照这样的顺序遍历二叉搜索树，遍历的各个节点的值就是递减的。
因此，遍历同时计数，遍历到第 k 个的时候，保存结果即可。
class Solution {
public:
int kthLargest(TreeNode* root, int k) {
int i = 0, res;
traversal(root, k, &i, &res);
return res;
}
private:
void traversal(TreeNode* node, int k, int *i, int *res){
if(node == nullptr){
return;
}
// 找到第 k 个节点后退出递归，不在继续遍历了。
if(*i >= k){
return;
}
traversal(node->right, k, i, res);
*i = *i + 1;
if(*i == k){
*res = node->val;
}
traversal(node->left, k, i, res);
}
};