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

解题思路

二叉搜索树的中序遍历结果是递增的，因此中序遍历的倒序就是递减的，也就是说，中序遍历倒序的第 k 个节点就是二叉搜索树的第 k 大节点，因此我们可以使用一个变量 target 来记录遍历时节点的序列号，当递归遍历到第 k 个节点时，直接返回该节点的值作为结果。

复杂度分析

• 时间复杂度：O(n)，其中 n 为树中节点的个数，在最差的情况下，树退化为链表（只有右子树），此时无论 k 的值为多少，递归深度都为 n ，因此时间复杂度为 O(n)。
• 空间复杂度：O(n)，最差的情况下，树退化为链表，递归所使用的栈空间为 O(n)。

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int target, res;

    public int kthLargest(TreeNode root, int k) {
        target = k;
        kthLargest(root);
        return res;
    }

    private void kthLargest(TreeNode root) {
        if (root == null || target == 0) {
            return;
        }
        kthLargest(root.right);
        if (--target == 0) {
            res = root.val;
            return;
        }
        kthLargest(root.left);
    }
}