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 <iostream>
2#include <unordered_map>
3#include <unordered_set>
4#include <queue>
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
class Solution {
public:
void buildGraph(TreeNode* node, unordered_map<int, vector<int>>& graph, int parent) {
if (!node) return;
if (parent > 0) {
graph[node->val].push_back(parent);
graph[parent].push_back(node->val);
}
buildGraph(node->left, graph, node->val);
buildGraph(node->right, graph, node->val);
}
int amountOfTime(TreeNode* root, int start) {
unordered_map<int, vector<int>> graph;
buildGraph(root, graph, -1);
unordered_set<int> visited;
queue<int> q;
q.push(start);
visited.insert(start);
int time = 0;
while (!q.empty()) {
for (int i = 0, n = q.size(); i < n; ++i) {
int node = q.front(); q.pop();
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push(neighbor);
}
}
}
if (!q.empty()) ++time;
}
return time;
}
};This C++ solution converts the binary tree into an adjacency list and then uses a BFS to calculate the time required to infect all nodes.
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 <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_NODES 100000
6
7typedef struct TreeNode {
8 int val;
9 struct TreeNode *left;
10 struct TreeNode *right;
11} TreeNode;
12
13int treeInfectionTimeDFS(TreeNode* root, int start) {
14 // Implementation logic goes here
15}This C solution deploys a DFS strategy to recursively compute time taken to infect each node, storing the maximum time found.