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.
Java Code :
class Solution {
public int amountOfTime(TreeNode root, int start) {
HashMap<TreeNode, TreeNode> mpp=new HashMap<>();
TreeNode target=bfsToMapParents(root,mpp,start);
return findMaxDistance(mpp, target);
}
private static int findMaxDistance(HashMap<TreeNode, TreeNode> mpp, TreeNode target) {
Queue<TreeNode> q = new LinkedList<>();
q.offer(target);
HashMap<TreeNode,Integer> vis = new HashMap<>();
vis.put(target, 1);
int maxi = 0;
while(!q.isEmpty()) {
int sz = q.size();
int fl = 0;
for(int i = 0;i<sz;i++) {
TreeNode node = q.poll();
if(node.left != null && vis.get(node.left) == null) {
fl = 1;
vis.put(node.left, 1);
q.offer(node.left);
}
if(node.right != null && vis.get(node.right) == null) {
fl = 1;
vis.put(node.right, 1);
q.offer(node.right);
}
if(mpp.get(node) != null && vis.get(mpp.get(node)) == null) {
fl = 1;
vis.put(mpp.get(node), 1);
q.offer(mpp.get(node));
}
}
if(fl == 1) maxi++;
}
return maxi;
}
TreeNode bfsToMapParents(TreeNode root,HashMap<TreeNode, TreeNode> mpp, int start) {
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
TreeNode res = new TreeNode(-1);
while(!q.isEmpty()) {
TreeNode node = q.poll();
if(node.val == start) res = node;
if(node.left != null) {
mpp.put(node.left, node);
q.offer(node.left);
}
if(node.right != null) {
mpp.put(node.right, node);
q.offer(node.right);
}
}
return res;
}
}
