6154. 感染二叉树需要的总时间 - 力扣（LeetCode）

6154. 感染二叉树需要的总时间 - 力扣（LeetCode）

---

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

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

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

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

示例 1：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YaZaNeDp-1661077386368)(https://assets.leetcode.com/uploads/2022/06/25/image-20220625231744-1.png)]

输入：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 。

1
2
3
4
5
6
7
8
9
10

示例 2：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QnSvhCfA-1661077386369)(https://assets.leetcode.com/uploads/2022/06/25/image-20220625231812-2.png)]

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

1
2
3
4

提示：

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

---

Solution

• 最大的感染时间
  • 要么是start节点的最大的子树高度
    • 递归的时候，在root->val== start，记录当前root的最大子树高度
  • 要么是从start出发到它的某个祖宗节点的路径长度+该祖宗节点的最大子树高度
    • 假设cur为start的祖宗节点，curDepth为cur节点的深度
      • 如果start在cur的左子树，那么结果为
        • ans = startDepth-curDepth+r
      • 如果start在cur的右子树，那么结果为
        • ans = startDepth-curDepth+l;
• 递归地取不同的节点，更新最大的ans，即可得到最终答案
• 再分析一下为什么上面的公式是可行的
  • 可以证明在递归地时候cur取到了start的非祖宗节点时，ans不会超过cur取start的祖宗节点得到的ans值
    • 当cur取start的某祖宗节点的另外一只子树的某节点时，上面得到的值永远小于cur取该祖宗节点得到的ans值
      • 因为，此时cur节点的深度恒大于等于该祖宗节点的深度，而cur节点的最大子树高度，恒小于等于该祖宗节点的最大子树高度
    • cur取start的子孙节点，上面的永远小于cur取start节点得到的值
      • 因为，此时cur节点的深度永远大于等于start节点的深度，而cur节点的最大子树高度，永远小于start节点的最大子树高度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans=0;
    int startDepth=-1;
    int dfs(TreeNode* root, int curDepth, int start){
        if(!root) return 0;
        if(root->val==start){
            startDepth = curDepth;
        }
        int l = dfs(root->left, curDepth+1, start);
        bool inLeft = startDepth!=-1;
        int r = dfs(root->right, curDepth+1, start);
        if(root->val==start){
            ans = max(ans, max(l, r));
        }
        else if(inLeft){
            ans = max(ans, startDepth - curDepth + r); // 注意加curdepth
        }
        else{
            ans = max(ans, startDepth - curDepth + l);
        }
        return max(l,r)+1;
    }
    int amountOfTime(TreeNode* root, int start) {
        dfs(root, 0, start);
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40