Sponsored
Sponsored
Approach 1: Breadth-First Search (BFS)
This approach involves simulating the infection spread using BFS, starting from the infected node. Each level of the BFS traversal represents one minute of infection spreading.
The steps are as follows:
Time Complexity: O(N) where N is the number of nodes; we visit each node once.
Space Complexity: O(N) to store the adjacency list and manage the queue.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public int AmountOfTime(TreeNode root, int start) {
var graph = new Dictionary<int, List<int>>();
BuildGraph(root, -1, graph);
var visited = new HashSet<int>();
var queue = new Queue<int>();
queue.Enqueue(start);
visited.Add(start);
int time = 0;
while (queue.Count > 0) {
int size = queue.Count;
for (int i = 0; i < size; i++) {
int node = queue.Dequeue();
foreach (var neighbor in graph[node]) {
if (!visited.Contains(neighbor)) {
visited.Add(neighbor);
queue.Enqueue(neighbor);
}
}
}
if (queue.Count > 0) time++;
}
return time;
}
private void BuildGraph(TreeNode node, int parent, Dictionary<int, List<int>> graph) {
if (node == null) return;
if (parent != -1) {
if (!graph.ContainsKey(node.val)) graph[node.val] = new List<int>();
if (!graph.ContainsKey(parent)) graph[parent] = new List<int>();
graph[node.val].Add(parent);
graph[parent].Add(node.val);
}
BuildGraph(node.left, node.val, graph);
BuildGraph(node.right, node.val, graph);
}
}In C#, we represent the binary tree as a graph and then apply a BFS to compute the infection spread time. This involves converting the tree nodes into adjacency lists and propagating the infection step by step.
Approach 2: Depth-First Search with Backtracking
In this method, we perform a depth-first search (DFS) to calculate the maximum distance (time) required to infect every node from the start node, utilizing backtracking to manage node revisits.
Steps include:
Time Complexity: O(N)
Space Complexity: O(N) for the recursion stack if the tree is unbalanced.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val)
3 this.left = (left===undefined ? null : left)
4 this.right = (right===undefined ? null : right)
5}
6
7var amountOfTime = function(root, start) {
8 let parentMap = new Map();
9 let startNode = null;
10
11 function findParents(node, parent) {
12 if (!node) return;
13 if (node.val === start) startNode = node;
14 if (parent) parentMap.set(node.val, parent);
15 findParents(node.left, node);
16 findParents(node.right, node);
17 }
18
19 function dfs(node, parent) {
20 if (!node) return 0;
21 let left = (node.left !== parent) ? dfs(node.left, node) : 0;
22 let right = (node.right !== parent) ? dfs(node.right, node) : 0;
23 let par = (parentMap.has(node.val) && parentMap.get(node.val) !== parent) ? dfs(parentMap.get(node.val), node) : 0;
24 return Math.max(left, Math.max(right, par)) + 1;
25 }
26
27 findParents(root, null);
28 return dfs(startNode, null) - 1;
29};In this JavaScript version, a dual recursion (DFS with parent tracking) calculates the maximum time for infection spread effectively, identifying each node's looping connections.