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

一、题目

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

二、示例

2.1> 示例 1:

2.2> 示例 2:

限制：

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

三、解题思路

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

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

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

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

voiddfs(TreeNodenode) {
 ... ...
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为例，看一下题目的具体处理过程。请见下图所示：

四、代码实现

classSolution {
intresult=-1, k=0;
publicintkthLargest(TreeNoderoot, intk) {
this.k=k;
dfs(root);
returnresult;
    }
voiddfs(TreeNodenode) {
if (node==null||result!=-1) return;
dfs(node.right);
if (--k==0) result=node.val;
dfs(node.left);
    }
}

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。