二叉搜索树的第k大节点

题目：

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

示例

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

思考：

提示

• 对于一棵二叉搜索树，每个根节点都大于它的左子结点，小于它的右子结点，所以它的中序遍历是(左、根、右)递增的

• 由此想到中序遍历的的倒序(右、根、左)是递减序列

• 想要找出其中第 k 大的节点的值，就需要计数，递归到第 k 个节点时返回

题解：

class Solution {

    int res, k;

    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }

    private void dfs(TreeNode root){
        if (root == null) return;
        dfs(root.right);

        if (k == 0) return;
        if (--k == 0) res = root.val;

        dfs(root.left);
    }
}