题目

• 给定一棵二叉搜索树，请找出其中第 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

代码

解法：遍历

class Solution {
public:
    // 右根左遍历 --> 倒序
    vector<int> res;
    int kthLargest(TreeNode* root, int k) {
        tranverse(root,k);
        return res[k-1];
    }
    void tranverse(TreeNode* root, int& k){
        if(root == NULL)    return;
        if(res.size() == k)    return;
        tranverse(root->right,k);
        res.push_back(root->val);
        tranverse(root->left,k);
    }
};

代码分析：一般做法应该就是这种，用右根左的顺序去遍历二叉搜索树，得到一个降序序列。这一步做优化

if(res.size() == k)    return;

拿到前 k 个就可以了，其他的用不着。但是我使用了 $O(n)$ 外部空间,应该是能优化掉的。

class Solution {
    int res=0;
    void dfs(TreeNode* root,int& k)
    {
        if(!root || k == 0) return;
        dfs(root->right,k);
        k--;
        if(k == 0) res = root->val;
        dfs(root->left,k);
    }
public:
    int kthLargest(TreeNode* root, int k) {
        dfs(root,k);
        return res;
    }
};

这样就好了，空复 $O(1)$

题目：二叉搜索树的第k大节点