题目描述

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

题解

二叉搜索树的中序遍历是递增序列，那么倒序就是递减序列。

中序遍历为“左、根、右”的顺序
中序遍历的倒序为“右、根、左”的顺序

// 打印中序遍历
void dfs(TreeNode root) {
    if(root == null) return;
    dfs(root.left); // 左
    System.out.println(root.val); // 根
    dfs(root.right); // 右
}

所以我们只要求出二叉搜索树的中序遍历倒序的第k个节点即可。

递归解析：

递归的终止条件：当节点为空的时候，越过了叶子节点，则直接返回;
递归右子树：dfs(root.right);
递归操作：先进行k - 1，然后判断 k 是否等于0，是则找到第k大的节点，将节点的值返回。
递归左子树：dfs(root.left);

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

public void dfs(TreeNode t) {
    if (t == null) {
        return;
    }
    dfs(t.right);
    if (k == 0) {
        return;
    }
    if (--k == 0) {
        res = t.val;
        return;
    }
    dfs(t.left);
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}