經典圖論題 Amount of Time for Binary Tree to Be Infected_2385

Gilly Stewart on Unsplash

題目敘述

題目會給定我們一棵二元數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 start exists 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:

[1] Python by DFS + BFS [w/ Comment]