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

一、题目

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

二、示例

2.1> 示例 1:

2.2> 示例 2:

限制：

• • 1 ≤ k ≤ 二叉搜索树元素个数

三、解题思路

根据题目描述，给定的是一棵二叉搜索树，那么这个二叉树具有的特征就是：

【若它的左子树不空】则左子树上所有结点的值均小于它的根结点的值； 【若它的右子树不空】则右子树上所有结点的值均大于它的根结点的值；

那么我们需要找到这棵二叉搜索树中第k大的节点值，那么其实就是需要我们能够以从大到小的顺序去遍历整棵树。即：采用先深度遍历树的右子节点，再深度遍历树的根节点，最后深度遍历树的左子节点。代码结构如下所示：

void dfs(TreeNode node) {
    ... ...
    dfs(node.right); // 深度遍历右子树
    node // 遍历根节点
    dfs(node.left); // 深度遍历左子树
    ... ...
}

那么，为了可以针对k值来判断是否满足第k大，那么我们还需要创建一个全局变量int k，它的默认值就是方法kthLargest(TreeNode root, int k)中第二个参数k，每当我们遍历到一个节点之后，就执行if (--k == 0)的判断，如果不满足，则继续深度遍历；如果满足了，则直接赋值给全局变量int result，那么result也就是我们本题的返回值。

其中，当我们找到了第k大的数时，我们就可以通过是否result != -1（默认result等于-1）来进行终止遍历的判断了。好了，上面就是本题的解题思路，下面我们还是按照惯例，以输入: root = [5,3,6,2,4,null,null,1], k = 3为例，看一下题目的具体处理过程。请见下图所示：

四、代码实现

class Solution {
    int result = -1, k = 0;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return result;
    }
    void dfs(TreeNode node) {
        if (node == null || result != -1) return;
        dfs(node.right);
        if (--k == 0) result = node.val;
        dfs(node.left);
    }
}