作者：whisper

链接：https://www.proprogrammar.com/article/877

声明：请尊重原作者的劳动，如需转载请注明出处

剑指 Offer 54. 二叉搜索树的第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 ≤ 二叉搜索树元素个数

难度：简单；标签：树；编程语言：C++

我的解法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        return kthLargest(root, &k);
    }
    
    int kthLargest(TreeNode* node, int* k){
        return node ? (kthLargest(node->right, k) ? *k : ((*k)-- == 1 ? *k = node->val : kthLargest(node->left, k))) : 0;
    }
};

自己写的，看了半天看不懂，大概就是找第K大，那先右后当前后左，先一直右，直到null（此时*k不变且大于0），那么当前(*k)--，为0时return，否则再向左，结合二叉树想像这个过程比较容易理解，这里这样写就是代码的trick（技巧）

二叉搜索树是有序的，如果找有序的第k个，就是先左后当前后右，这里是第K大，所以是先右后当前后左

其它解法

class Solution {
    public:
        int rst;
        int cout;
        int kthLargest(TreeNode* root, int k) {
            cout = k;
            re_inorder(root);
            return rst;
        }
        void re_inorder(TreeNode* cur){
            if(cur == NULL || cout==0){
                return;
            }
            re_inorder(cur->right);
            if(--cout==0){
                rst = cur->val;
                return;
            }
            re_inorder(cur->left);
        }
    };

上面就比较好理解了，反中序遍历，从大到小，返回遍历到的第K个数

亲爱的读者：有时间可以点赞评论一下