You are given the root of a binary tree with unique values, and an integer start. At minute 0, an infection starts from the node with value start.
Each minute, a node becomes infected if:
- The node is currently uninfected.
- The node is adjacent to an infected node.
Return the number of minutes needed for the entire tree to be infected.
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, 105]. 1 <= Node.val <= 105- Each node has a unique value.
- A node with a value of
start exists in the tree.
Solution:
start exists in the tree.The solution to this question is straightforward. If you know graphs, you can answer this question in less than a minute. We can app DFS and can get the answer, but how we can do that as this is a tree? Either we can make a new graph with this tree or we can traverse the tree once and then store the parent node of all the nodes. Then we can simply apply DFS on this.
1 Comments
#include
ReplyDeleteusing namespace std;
int main(){
cout<<"Welcome to FCFS \n";
cout<<"Enter the number of Processes: ";
int k=1;
cin>>k;
int pid,arrivalTime,burstTime;
vector>process;
while(k--){
cout<<"Enter Process ID: ";
cin>>pid;
cout<<"Enter Arrival Time: ";
cin>>arrivalTime;
cout<<"Enter the Burst Time: ";
cin>>burstTime;
process.push_back({pid,arrivalTime,burstTime});
}
int st=0;
cout<<"Process No: Arrival Time: Burst Time: Completion Time: Turn Around Time: Waiting Time: Response Time:\n";
for (int i = 0; i < process.size(); i++)
{
vectorv=process[i];
int ct=max(v[1]+v[2],st+v[2]);
cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<" "<<ct<<" "<<ct-v[1]<<" "<<abs(st-v[1])<<" "<<max(0,st-v[1])<<endl;
st=ct;
}
return 0;
}
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.