​LeetCode解法汇总2385. 感染二叉树需要的总时间

这篇具有很好参考价值的文章主要介绍了​LeetCode解法汇总2385. 感染二叉树需要的总时间。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:. - 力扣(LeetCode)

描述:

给你一棵二叉树的根节点 root ,二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟,感染 将会从值为 start 的节点开始爆发。

每分钟,如果节点满足以下全部条件,就会被感染:

  • 节点此前还没有感染。
  • 节点与一个已感染节点相邻。

返回感染整棵树需要的分钟数

示例 1:

​LeetCode解法汇总2385. 感染二叉树需要的总时间,编程题,leetcode,算法,职场和发展

输入:root = [1,5,3,null,4,10,6,9,2], start = 3
输出:4
解释:节点按以下过程被感染:
- 第 0 分钟:节点 3
- 第 1 分钟:节点 1、10、6
- 第 2 分钟:节点5
- 第 3 分钟:节点 4
- 第 4 分钟:节点 9 和 2
感染整棵树需要 4 分钟,所以返回 4 。

示例 2:

​LeetCode解法汇总2385. 感染二叉树需要的总时间,编程题,leetcode,算法,职场和发展

输入:root = [1], start = 1
输出:0
解释:第 0 分钟,树中唯一一个节点处于感染状态,返回 0 。

提示:

  • 树中节点的数目在范围 [1, 105] 内
  • 1 <= Node.val <= 105
  • 每个节点的值 互不相同
  • 树中必定存在值为 start 的节点

解题思路:

首先,构造递归方法,方法的返回值为当前节点是否包含start节点。如果找到start节点,则计算这个节点为出发点的最远路径,这是备选值1。上层递归方法中,分左右节点查询。如果左节点中包含start节点,路径为当前节点右节点的最远路径+start节点和当前节点的层级差,这是备选值2。右节点包含也是类似的原理。持续往上递归,找出所有备选值2。求出所有备选值中最大值即可。文章来源地址https://www.toymoban.com/news/detail-856976.html

代码:

class Solution {
    int leafLevel = 0;
    int maxPath = 0;

    public int amountOfTime(TreeNode root, int start) {
        searchStartNode(root, start, 0);
        return maxPath;
    }


    boolean searchStartNode(TreeNode node, int start, int level) {
        if (node == null) {
            return false;
        }
        if (node.val == start) {
            maxPath = searchLevel(node, 0) - 1;
            leafLevel = level;
            return true;
        }
        if (searchStartNode(node.left, start, level + 1)) {
            maxPath = Math.max(maxPath, leafLevel - level + searchLevel(node.right, 0));
            return true;
        }
        if (searchStartNode(node.right, start, level + 1)) {
            maxPath = Math.max(maxPath, leafLevel - level + searchLevel(node.left, 0));
            return true;
        }
        return false;
    }

    int searchLevel(TreeNode node, int level) {
        if (node == null) {
            return level;
        }
        level++;
        return Math.max(searchLevel(node.left, level), searchLevel(node.right, level));
    }
}

到了这里,关于​LeetCode解法汇总2385. 感染二叉树需要的总时间的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java LeetCode篇-深入了解二叉树经典解法(三种方式实现:获取二叉树的最大深度)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 对称二叉树         1.1 判断对称二叉树实现思路         1.2 代码实现:判断对称二叉树         2.0 二叉树的最大深度         2.1 使用递归实现获取二叉树的最大深度思

    2024年02月05日
    浏览(77)
  • 【算法】【算法杂谈】折纸问题(完全二叉树解法)

    当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识! 原问题 一张纸从下往上对折之后,出现一条折痕,该折痕凸起向下,所以叫“下折痕”,反之如果摊开之后,凸起向上,则叫

    2024年02月01日
    浏览(39)
  • ​LeetCode解法汇总2490. 回环句

    https://github.com/September26/java-algorithms 力扣 句子  是由单个空格分隔的一组单词,且不含前导或尾随空格。 例如, \\\"Hello World\\\" 、 \\\"HELLO\\\" 、 \\\"hello world hello world\\\"  都是符合要求的句子。 单词  仅  由大写和小写英文字母组成。且大写和小写字母会视作不同字符。 如果句子满足下

    2024年02月12日
    浏览(43)
  • ​LeetCode解法汇总2544. 交替数字和

    https://github.com/September26/java-algorithms 给你一个正整数  n  。 n  中的每一位数字都会按下述规则分配一个符号: 最高有效位  上的数字分配到  正  号。 剩余每位上数字的符号都与其相邻数字相反。 返回所有数字及其对应符号的和。 示例 1: 示例 2: 示例 3: 提示: 1 = n

    2024年02月16日
    浏览(34)
  • ​LeetCode解法汇总2679. 矩阵中的和

    https://github.com/September26/java-algorithms 给你一个下标从  0  开始的二维整数数组  nums  。一开始你的分数为  0  。你需要执行以下操作直到矩阵变为空: 矩阵中每一行选取最大的一个数,并删除它。如果一行中有多个最大的数,选择任意一个并删除。 在步骤 1 删除的所有数字

    2024年02月16日
    浏览(42)
  • ​LeetCode解法汇总1177. 构建回文串检测

    https://github.com/September26/java-algorithms 给你一个字符串  s ,请你对  s  的子串进行检测。 每次检测,待检子串都可以表示为  queries[i] = [left, right, k] 。我们可以  重新排列  子串  s[left], ..., s[right] ,并从中选择  最多   k  项替换成任何小写英文字母。  如果在上述检测过程

    2024年02月09日
    浏览(28)
  • ​LeetCode解法汇总88. 合并两个有序数组

    https://github.com/September26/java-algorithms 给你两个按  非递减顺序  排列的整数数组  nums1   和  nums2 ,另有两个整数  m  和  n  ,分别表示  nums1  和  nums2  中的元素数目。 请你  合并   nums2   到  nums1  中,使合并后的数组同样按  非递减顺序  排列。 注意: 最终,合并

    2024年02月12日
    浏览(45)
  • ​LeetCode解法汇总LCP 50. 宝石补给

    GitHub - September26/java-algorithms: 算法题汇总,包含牛客,leetCode,lintCode等网站题目的解法和代码,以及完整的mode类,甚至链表代码生成工具都有提供。 欢迎各位勇者来到力扣新手村,在开始试炼之前,请各位勇者先进行「宝石补给」。 每位勇者初始都拥有一些能量宝石, 

    2024年02月07日
    浏览(41)
  • ​LeetCode解法汇总2865. 美丽塔 I

    https://github.com/September26/java-algorithms 给你一个长度为  n  下标从  0  开始的整数数组  maxHeights  。 你的任务是在坐标轴上建  n  座塔。第  i  座塔的下标为  i  ,高度为  heights[i]  。 如果以下条件满足,我们称这些塔是  美丽  的: 1 = heights[i] = maxHeights[i] heights  是一

    2024年01月25日
    浏览(50)
  • ​LeetCode解法汇总344. 反转字符串

    https://github.com/September26/java-algorithms 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组  s  的形式给出。 不要给另外的数组分配额外的空间,你必须 原地修改输入数组 、使用 O(1) 的额外空间解决这一问题。 示例 1: 示例 2: 提示: 1 = s.length = 105

    2024年02月14日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包