题解 | #二叉树之寻找第k大#

二叉树之寻找第k大

https://www.nowcoder.com/practice/8e5f73fa3f1a407eb7d0b0d7a105805e

一、知识点:

中序遍历、递归、二叉树

二、文字分析:

反向中序遍历的递归实现:我们首先定义了两个全局变量count和result,分别用于记录当前遍历的节点是第几个节点和第k大的牛的编号。通过递归方式获取二叉搜索树的节点总数,并根据节点总数计算目标节点的计数器值。然后,通过递归方式进行反向中序遍历,首先递归遍历右子树,然后将计数器加1,并判断计数器的值是否等于目标值。如果是,则更新result为当前节点的值,并立即返回。如果不是,则继续递归遍历左子树。

时间复杂度为O(N),空间复杂度为O(N)。

三、编程语言:

java

四、正确代码:

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    private int count = 0; // 计数器,记录当前节点是第几个节点
    private int result = 0; // 记录第k大的牛的编号
    
    public int kthLargest(TreeNode root, int k) {
        reverseInorderTraversal(root, k); // 反向中序遍历
        
        return result;
    }
    
    private void reverseInorderTraversal(TreeNode node, int k) {
        if (node == null) {
            return;
        }
        
        reverseInorderTraversal(node.right, k);
        
        count++;
        if (count == k) {
            result = node.val;
            return;
        }
        
        reverseInorderTraversal(node.left, k);
    }
}

全部评论

相关推荐

OPSL:钱确实给的多,但是追责这一点比较迷惑…3个月具体如何计算呢?出勤天数30*3吗?还是21*3呢?万一中间学校有安排怎么办呢?这个得多问一问呀
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务