题目描述

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

题解

由于二叉搜索树的中序遍历是一个递增序列，因此按中序遍历即可。

注意这里是求第 k 大的节点，而不是第 k 小，因此先遍历右子树，再遍历根节点，最后遍历左子树。

class Solution {
    int count = 1, res;
    public int kthLargest(TreeNode root, int k) {
        kthLargestHelper(root, k);
        return res;
    }

    public void kthLargestHelper(TreeNode root, int k) {
        if (root == null)
            return;
        kthLargestHelper(root.right, k);

        // 中序遍历的逻辑
        if (count == k) {
            res = root.val;
            count++;
            return;
        }
        count++;

        kthLargestHelper(root.left, k);
    }
}