剑指 Offer 54. 二叉搜索树的第k大节点

剑指 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

翻转中序遍历，右->中->左

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        if (!root)
            return -1;
        int n = 0;
        TreeNode* ans = Ans(root, k, n);
        return ans->val;
    }
    TreeNode* Ans(TreeNode* root, int k,int &n) {
        TreeNode* a = NULL;
        if (root->right) {
            a = Ans(root->right, k, n);
            
            if (n == k && a)
                return a;
        }
        n++;
        if (n == k)
            return root;
        
        if (root->left) {
            a=Ans(root->left, k, n);
            if (n == k && a)
                return a;
        }
        return NULL;
    }
};