題目敘述
題目會給定我們一棵二元數Binary Tree的根結點。
並且給定感染的病毒源節點位置，每個單位時間，可以向相鄰的節點感染一次，問我們需要多少時間去感染整棵樹?
題目的原文敘述測試範例
Example 1:
Input: root = [1,5,3,null,4,10,6,9,2], start = 3
Output: 4
Explanation: The following nodes are infected during:
- Minute 0: Node 3
- Minute 1: Nodes 1, 10 and 6
- Minute 2: Node 5
- Minute 3: Node 4
- Minute 4: Nodes 9 and 2
It takes 4 minutes for the whole tree to be infected so we return 4.
Example 2:
Input: root = [1], start = 1
Output: 0
Explanation: At minute 0, the only node in the tree is infected so we return 0.
約束條件
Constraints:
- The number of nodes in the tree is in the range
[1, 10^5]. 1 <= Node.val <= 10^5- Each node has a unique value.
- A node with a value of
startexists in the tree.
演算法
其實，二元樹Binary tree本身也是一種圖Graph，轉換成圖之後，要解開就非常容易了。
因為，最少需要多少時間去感染整棵樹 = 最少需要多少時間，去拜訪整張圖。
我們就把原本感染的問題映射到圖上的拜訪Traversal問題去解開來。
第一步:
先用DFS深度優先演算法建立整張圖，也就是把二元樹的連結關係用相鄰陣列的方式來表達。
第二步:
再用BFS廣度優先演算法，從感染的起點開始，拜訪整張圖，所需的時間就是感染整顆樹的時間。(BFS先天具有點波源擴散的性質)
程式碼
class Solution:
def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
graph = defaultdict(list)
# Build connected graph for binary tree in DFS
def dfs(node, parent):
if not node:
return
if parent:
graph[node.val].append(parent.val)
graph[parent.val].append(node.val)
dfs(node.left, node)
dfs(node.right, node)
return
#--------------------------------------
dfs(root, None)
# Start infection from start node, with BFS, which naturally has shortest path
bfs_queue = deque( [ (start, 0) ] )
visited = set([start])
while bfs_queue:
for _ in range( len(bfs_queue) ):
cur, step = bfs_queue.popleft()
for neighbor in graph[cur]:
if neighbor not in visited:
visited.add(neighbor)
bfs_queue.append( (neighbor, step+1) )
return step
關鍵知識點
二元樹Binary tree本身也是一種圖Graph，轉換成圖之後，要解開就非常容易了。
因為，最少需要多少時間去感染整棵樹 = 最少需要多少時間，去拜訪整張圖。
另外，BFS先天具有點波源擴散的性質，所以在無權重的圖中，也具有尋找最短路徑的特質。在這題，就是利用這個特質，來找出最少需要多少時間來拜訪整張圖(相當於感染整棵樹)。
複雜度分析
時間複雜度:
O(n) DFS和BFS拜訪整張圖，每個節點至多分別拜訪一次，O(2n) = O(n)。
空間複雜度:
O(n) DFS和BFS拜訪整張圖，最大深度發生在整棵樹向左歪斜或者向右歪斜時 = O(n)。
另外，建立graph的相連矩陣時，也需要耗費O(n)的空間。
Reference:
