目录链接:
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目:
https://github.com/September26/java-algorithms
原题链接:. - 力扣(LeetCode)
描述:
给你一棵二叉树的根节点 root
,二叉树中节点的值 互不相同 。另给你一个整数 start
。在第 0
分钟,感染 将会从值为 start
的节点开始爆发。
每分钟,如果节点满足以下全部条件,就会被感染:
- 节点此前还没有感染。
- 节点与一个已感染节点相邻。
返回感染整棵树需要的分钟数。
示例 1:
输入: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:
输入:root = [1], start = 1 输出:0 解释:第 0 分钟,树中唯一一个节点处于感染状态,返回 0 。
提示:文章来源:https://www.toymoban.com/news/detail-856976.html
- 树中节点的数目在范围
[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模板网!