乐趣区

关于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;
    }
};
退出移动版