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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_NODES
This C solution creates a graph-like structure from the binary tree and performs a breadth-first search from the start node to determine the infection spread time.
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.
1#include <iostream>
2#include <unordered_map>
3#include <unordered_set>
4#include <vector>
5using namespace std;
6
7struct TreeNode {
8 int val;
9 TreeNode *left;
10 TreeNode *right;
11 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12};
13
14class Solution {
15public:
16 int amountOfTime(TreeNode* root, int start) {
17 unordered_map<int, TreeNode*> parentTrack;
18 TreeNode* startNode = nullptr;
19 findParent(root, parentTrack, startNode, start);
20 return dfs(startNode, NULL, parentTrack);
21 }
22
23 void findParent(TreeNode* node, unordered_map<int, TreeNode*>& parents, TreeNode*& target, int start) {
24 if (!node) return;
25 if (node->val == start) {
26 target = node;
27 }
28 if (node->left) {
29 parents[node->left->val] = node;
30 findParent(node->left, parents, target, start);
31 }
32 if (node->right) {
33 parents[node->right->val] = node;
34 findParent(node->right, parents, target, start);
35 }
36 }
37
38 int dfs(TreeNode* node, TreeNode* parent, unordered_map<int, TreeNode*>& parents) {
39 if (!node) return 0;
40 int left = node->left != parent ? dfs(node->left, node, parents) : 0;
41 int right = node->right != parent ? dfs(node->right, node, parents) : 0;
42 int par = parents.count(node->val) && parents[node->val] != parent ? dfs(parents[node->val], node, parents) : 0;
43 return max(left, max(right, par)) + 1;
44 }
45};This C++ implementation makes use of backtracking within DFS to evaluate various potential infection paths and calculate infection time swiftly and comprehensively.