# 2385. Amount of Time for Binary Tree to Be Infected
###### tags: `Leetcode` `Medium` `Tree` `BFS`
Link: https://leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected/
## 思路
先找到每个node的parent
然后对整个graph开始层序遍历
## Code

class Solution {
    public int amountOfTime(TreeNode root, int start) {
        Map<TreeNode, TreeNode> parents = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode startNode = null;
        q.add(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            if(curr.val==start){
                startNode = curr;
            }
            if(curr.left!=null){
                parents.put(curr.left, curr);
                q.add(curr.left);
            }
            if(curr.right!=null){
                parents.put(curr.right, curr);
                q.add(curr.right);
            }
        }
        
        Set<TreeNode> visited = new HashSet<>();
        q.add(startNode);
        visited.add(startNode);
        int time = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                TreeNode curr = q.poll();
                if(curr.left!=null && !visited.contains(curr.left)){
                    q.add(curr.left);
                    visited.add(curr.left);
                }
                if(curr.right!=null && !visited.contains(curr.right)){
                    q.add(curr.right);
                    visited.add(curr.right);
                }
                if(parents.containsKey(curr) && !visited.contains(parents.get(curr))){
                    q.add(parents.get(curr));
                    visited.add(parents.get(curr));
                }
            }
            time++;
        }
        return time-1;
    }
}