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.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val)
3
In JavaScript, this solution models the binary tree as an undirected graph, using adjacency lists, then employs a BFS to simulate infection propagation through these connections.
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.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode(int x) { val = x; }
8}
9
10class Solution {
11 private Map<Integer, TreeNode> parentMap = new HashMap<>();
12 private TreeNode targetNode = null;
13
14 public int amountOfTime(TreeNode root, int start) {
15 findParents(root, null, start);
16 return dfs(targetNode, null);
17 }
18
19 private void findParents(TreeNode node, TreeNode parent, int start) {
20 if (node == null) return;
21 if (node.val == start) {
22 targetNode = node;
23 }
24 if (parent != null) {
25 parentMap.put(node.val, parent);
26 }
27 findParents(node.left, node, start);
28 findParents(node.right, node, start);
29 }
30
31 private int dfs(TreeNode node, TreeNode parent) {
32 if (node == null) return 0;
33 int left = (node.left != parent) ? dfs(node.left, node) : 0;
34 int right = (node.right != parent) ? dfs(node.right, node) : 0;
35 int par = (parentMap.containsKey(node.val) && parentMap.get(node.val) != parent) ? dfs(parentMap.get(node.val), node) : 0;
36 return Math.max(left, Math.max(right, par)) + 1;
37 }
38}Java approach for DFS with backtracking; The key here is to compute the maximum time via recursive traversal, making use of a parent map to track node relations.