树形dp，LeetCode 2385. 感染二叉树需要的总时间

一、题目

1、题目描述

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

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

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

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

2、接口描述

python3

​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:

cpp

​

/**
 * 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 amountOfTime(TreeNode* root, int start) {
        
    }
};

3、原题链接

2385. 感染二叉树需要的总时间

二、解题报告

1、思路分析

答案很明显就是求start向上最大距离和向下最大距离中大的那个

这个还是很好求的，我们可以两次dfs，开两个数组记录下值，就是一个换根dp，换根到start的时候就返回答案即可

不过更优雅的做法是，我们发现答案来自两部分：start向下最大距离，根节点到start的距离加上从另一颗子树向下的最大距离

那么实际上我们进行一次dfs即可

如果找到start或者子树中找到start，我们向上返回深度的时候就返回到达start的距离

如果没找到，就返回到最远子节点的距离的相反数

2、复杂度

时间复杂度： O(n) 空间复杂度：O(n)

3、代码详解

python3

​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        ret = 0
        def dfs(rt: Optional[TreeNode]) -> int:
            if rt is None:
                return 0
            L = dfs(rt.left)
            R = dfs(rt.right)
            nonlocal ret
            if rt.val == start:
                ret = max(ret, -min(L, R))
                return 1
            if L > 0 or R > 0:
                ret = max(ret, abs(L) + abs(R))
                return max(L, R) + 1
            return min(L, R) - 1
        dfs(root)
        return ret

cpp

​

/**
 * 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 ret, start;
    int dfs(TreeNode* root){
        if(!root) return 0;
        int L = dfs(root->left), R = dfs(root->right);
        if(root->val == start){
            ret = -min(L, R);
            return 1;
        }
        if(L > 0 || R > 0){
            ret = max(ret, abs(L) + abs(R));
            return max(L, R) + 1;
        }
        return min(L, R) - 1;
    }
    int amountOfTime(TreeNode* root, int start) {
        ret = 0, this->start = start;
        dfs(root);
        return ret;
    }
};