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

1 题目

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

作者：画手大鹏
链接：https://leetcode-cn.com/leetbook/read/illustrate-lcof/xspy85/
来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2 中序遍历

该方法为先使用一个集合类容器放置该树的中序遍历的结果序列，因为二叉搜索树的中序遍历是一个升序的序列，那么第$k$大的数则为第$list.size()-k$个数。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthLargest(TreeNode root, int k) {
        List<Integer> res = new ArrayList<>();
        inOrder(root, res);
        return res.get(res.size() - k);
    }

    private void inOrder(TreeNode root, List<Integer> res) {
        if (root == null)
            return;
        inOrder(root.left, res);
        res.add(root.val);
        inOrder(root.right, res);
    }
}

这种算法的时间复杂度和空间复杂度都是$O(n)$，其中$n$是二叉搜索树的节点个数，那么这种方法并没有利用二叉搜索树的性质。

3 改进版

我们知道二叉搜索树的左子树的所有值都小于根节点的值，右子树的所有值都大于根节点的值。且中序遍历的序列是一个升序的序列，那么中序遍历的顺序是left->root->right。这种遍历方式决定了中序遍历的结果是一个升序的序列，题目中要求返回第$k$大的数，那么就是中序遍历序列从后往后算起第$k$个数。
我们可以不用遍历完这棵树，只需要遍历$k$次即可，我们修改树的遍历次序，改为right->root-left。那么遍历的最终的结果就是一个降序的序列。我们定义一个全局的索引，判断当前遍历到了第几个节点，当遍历到第$k$个节点时，我们就可以结束遍历返回结果。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int index = 0, res = 0;
    public int kthLargest(TreeNode root, int k) {
        this.index = k;
        dfs(root);
        return res;
    }

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

        dfs(root.right);
        index--;
        if (index == 0) {
            res = root.val;
            return;
        }
        dfs(root.left);
    }
}