关于leetcode:每日一练26二叉搜索树的第k大节点

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;    }};