题目描述

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

算法1

由二叉搜索树的定义可得知
根的右子树的节点都比根节点大
根的左子树的节点都比根节点小
那么我们按照右 根 左的次序遍历树
就可以得到由大到小的节点排序序列
我们输出倒数第K个节点就是第K大的节点

C++ 代码

class Solution {
public:
    int ans = 0;  
    int kk;  
    void dfs(TreeNode* root)
    {
        if(root==NULL)  return;
        dfs(root->right);
        kk -= 1;
        if(kk==0){   ans = root->val;}
        dfs(root->left);
        return;
    }

    int kthLargest(TreeNode* root, int k) {
        kk = k;
        dfs(root);
        return ans;
    }
};

我的视频空间