LeetCode-2385. 感染二叉树需要的总时间【树 深度优先搜索 广度优先搜索 二叉树】

题目描述：

给你一棵二叉树的根节点 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 。

提示：

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

解题思路一：记录父节点 + DFS

设 v 是离 start 最远的节点，返回 start 到 v 的距离。例如示例 1 中节点 9（或者节点 2）离 start=3 最远，二者距离为 4。

这里不想使用nonlocal可以使用列表

# 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:
        fa = {}
        start_node = [None]
        def dfs(node, from_):
            if node is None:
                return
            fa[node] = from_ # 记录每个节点的父节点
            if node.val == start: # 找到 start
                # nonlocal start_node
                start_node[0] = node
            dfs(node.left, node)
            dfs(node.right, node)
        dfs(root, None)
        def maxDepth(node, from_):
            if node is None:
                return -1 # 注意这里是 -1，因为 start 的深度为 0
            return max(maxDepth(x, node) for x in (node.left, node.right, fa[node]) if x != from_) + 1
        return maxDepth(start_node[0], start_node[0])
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

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

解题思路二：

class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        ans = 0
        def dfs(node: Optional[TreeNode]) -> (int, bool):
            if node is None:
                return 0, False
            l_len, l_found = dfs(node.left)
            r_len, r_found = dfs(node.right)
            nonlocal ans
            if node.val == start:
                # 计算子树 start 的最大深度
                # 注意这里和方法一的区别，max 后面没有 +1，所以算出的也是最大深度
                ans = max(l_len, r_len)
                return 1, True  # 找到了 start
            if l_found or r_found:
                # 只有在左子树或右子树包含 start 时，才能更新答案
                ans = max(ans, l_len + r_len)  # 两条链拼成直径
                # 保证 start 是直径端点
                return (l_len if l_found else r_len) + 1, True
            return max(l_len, r_len) + 1, False
        dfs(root)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

解题思路三：深度优先搜索建图 + 广度优先搜索求感染时间【最容易理解】

根据题意，需求出值为 start 的节点到其他节点最远的距离。树中的最远距离可以用广度优先搜索来求解。但是 start 不一定为根节点，我们需要先将树的结构用深度优先搜索解析成无向图，再用广度优先搜索来求最长距离。代码中 graph 即为邻接表，用一个哈希表来表示。哈希表的键为节点值，值为其相邻节点的值组成的列表。建完表后用广度优先搜索求最长距离。

# 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:
        graph = collections.defaultdict(list)
        def dfs(node):
            for child in [node.left, node.right]:
                if child:
                    graph[child.val].append(node.val)
                    graph[node.val].append(child.val)
                    dfs(child)
        dfs(root)

        q = deque([[start, 0]])
        visited = set([start])
        time = 0
        while q:
            nodeVal, time = q.popleft()
            for childVal in graph[nodeVal]:
                if childVal not in visited:
                    q.append([childVal, time + 1])
                    visited.add(childVal)
        return time
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

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

---

创作不易，观众老爷们请留步… 动起可爱的小手，点个赞再走呗 (๑◕ܫ￩๑) 欢迎大家关注笔者，你的关注是我持续更博的最大动力

原创文章，转载告知，盗版必究

---

---

---

♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠