BFS - 20200202

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while(!queue.isEmpty()){
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            
            for(int i = 0; i< size; i++){
                TreeNode head = queue.poll();
                level.add(head.val);
                if(head.left != null){
                    queue.offer(head.left);
                }
                
                if(head.right != null){
                    queue.offer(head.right);
                }
            }
            
            res.add(level);
        }
        
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        
        List<List<Integer>> res = new ArrayList<>();
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode head = queue.poll();
                level.add(head.val);
                
                if(head.left != null){
                    queue.offer(head.left);
                }
                
                if(head.right != null){
                    queue.offer(head.right);
                }
            }
            res.add(level);
        }
        
        Collections.reverse(res);
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        int count = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            
            for(int i = 0; i < size; i++){
                TreeNode head = queue.poll();
                level.add(head.val);
                
                if(head.left != null){
                    queue.offer(head.left);
                }
                
                if(head.right != null){
                    queue.offer(head.right);
                }
            }
            
            if(count % 2 == 1){
                Collections.reverse(level);
            }
            
            res.add(level);
            count++;
        }
        
        return res;
    }
}

public class Solution {
    /**
     * @param n: An integer
     * @param edges: a list of undirected edges
     * @return: true if it‘s a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        // write your code here
        if(n == 0){
            return false;
        }

        if(edges.length != n-1){
            return false;
        }

        Map<Integer,Set<Integer>> neighbourMap = getNeighbourHoods(n,edges);

        Queue<Integer> queue = new LinkedList<Integer>();
        Set<Integer> existedNodes = new HashSet<>();
        
        queue.add(0);
        existedNodes.add(0);
        
        while(!queue.isEmpty()){
            Integer node = queue.poll();
            Set<Integer> neighbours = neighbourMap.get(node);
            
            for(Integer neighbour : neighbours){
                if(existedNodes.contains(neighbour)){
                    continue;
                }
                
                queue.offer(neighbour);
                existedNodes.add(neighbour);
            }
        }
        
        return existedNodes.size() == n;
    }

    Map<Integer, Set<Integer>> getNeighbourHoods(int n, int[][] edges){
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int i=0; i < n; i++){
            map.put(i, new HashSet<Integer>());
        }

        for(int i = 0; i< edges.length; i++){
            int u = edges[i][0];
            int v = edges[i][1];
            map.get(u).add(v);
            map.get(v).add(u);
        }

        return map;
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/
class Solution {
    public Node cloneGraph(Node node) {
        if(node == null){
            return null;
        }

        //get all nodes
        List<Node> allNodes = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        Set<Node> nodeSet = new HashSet<>();

        queue.offer(node);
        nodeSet.add(node);

        while(!queue.isEmpty()){
            Node n = queue.poll();
            for(Node neighbor: n.neighbors){
                if(!nodeSet.contains(neighbor)){
                    queue.offer(neighbor);
                    nodeSet.add(neighbor);
                }
            }
        }

        allNodes = new ArrayList<Node>(nodeSet);

        //copy nodes and mark the new/old nodes‘ corresponding
        Map<Node,Node> oldNewMap = new HashMap<>();
        for(Node n:allNodes){
            oldNewMap.put(n, new Node(n.val));
        }

        //copy neighbours
        for(Node n:allNodes){
            Node newNode = oldNewMap.get(n);
            for(Node neighbor:n.neighbors){
                newNode.neighbors.add(oldNewMap.get(neighbor));
            }
        }
        
        return oldNewMap.get(node);


    }
}

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        //construct neighourMap and get indegree
        Map<Integer,ArrayList<Integer>> neighourMap = new HashMap<>();
        Map<Integer,Integer> degreeMap = new HashMap<>();

        for(int i = 0; i< numCourses; i++){
            neighourMap.put(i, new ArrayList<Integer>());
        }
        
        for(int i = 0; i<prerequisites.length; i++){
            neighourMap.get(prerequisites[i][1]).add(prerequisites[i][0]);
            if(!degreeMap.containsKey(prerequisites[i][0])){
                degreeMap.put(prerequisites[i][0],1);
            }else{
                degreeMap.put(prerequisites[i][0], degreeMap.get(prerequisites[i][0])+1);
            }
        }
        
        //topological sorting
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i< numCourses; i++){
            if(!degreeMap.containsKey(i)){
                queue.offer(i);
                count++;
            }
        }
        
        while(!queue.isEmpty()){
            Integer course = queue.poll();
            for(Integer nextCourse: neighourMap.get(course)){
                degreeMap.put(nextCourse,degreeMap.get(nextCourse)-1);
                
                if(degreeMap.get(nextCourse)==0){
                    queue.offer(nextCourse);
                    count++;
                }
            }
        }
        
        return count == numCourses;
        
    }
}

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {

        //construct neighourMap and get indegree
        Map<Integer,ArrayList<Integer>> neighourMap = new HashMap<>();
        Map<Integer,Integer> degreeMap = new HashMap<>();
        int[] res = new int[numCourses];

        for(int i = 0; i< numCourses; i++){
            neighourMap.put(i, new ArrayList<Integer>());
        }

        for(int i = 0; i<prerequisites.length; i++){
            neighourMap.get(prerequisites[i][1]).add(prerequisites[i][0]);
            if(!degreeMap.containsKey(prerequisites[i][0])){
                degreeMap.put(prerequisites[i][0],1);
            }else{
                degreeMap.put(prerequisites[i][0], degreeMap.get(prerequisites[i][0])+1);
            }
        }

        //topological sorting
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i< numCourses; i++){
            if(!degreeMap.containsKey(i)){
                queue.offer(i);
                res[count] = i;
                count++;
            }
        }

        while(!queue.isEmpty()){
            Integer course = queue.poll();
            for(Integer nextCourse: neighourMap.get(course)){
                degreeMap.put(nextCourse,degreeMap.get(nextCourse)-1);

                if(degreeMap.get(nextCourse)==0){
                    queue.offer(nextCourse);
                    res[count] = nextCourse;
                    count++;
                }
            }
        }

        if(count == numCourses){
            return res;    
        }
        
        return new int[0];

    }
}

class Point{
    int x;
    int y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

class Solution {

    int[] directX = {0, 1, 0, -1};
    int[] directY = {1, 0, -1, 0};
    public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0){
            return 0;
        }

        int r = grid.length;
        int c = grid[0].length;

        if(c == 0){
            return 0;
        }

        int count = 0;
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                if(grid[i][j] == ‘1‘){
                    BFS(grid,new Point(i,j));
                    count++;
                }
            }
        }
        
        return count;
    }

    public void BFS(char[][] grid, Point center){
        Queue<Point> queue = new LinkedList<>();
        queue.offer(center);
        grid[center.x][center.y] = ‘0‘;
        
        while(!queue.isEmpty()){
            Point head = queue.poll();
            for(int i = 0; i< 4; i++){
                Point point = new Point(head.x + directX[i],head.y+directY[i]);
                if(!isInMatrix(point,grid)){
                    continue;
                }
                
                if(grid[point.x][point.y]== ‘1‘){
                    queue.offer(point);
                    grid[point.x][point.y] = ‘0‘;
                }
            }
        }
    }
    
    public boolean isInMatrix(Point point, char[][]grid){
        int r = grid.length;
        int c = grid[0].length;
        return point.x>=0 && point.x<r && point.y>=0 && point.y<c;
    }
}

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(beginWord == null || endWord == null || wordList == null){
            return 0;
        }

        if(beginWord.equals(endWord)){
            return 1;
        }

        Set<String> dict = new HashSet<>();
        for(String s: wordList){
            dict.add(s);
        }

        // dict.add(endWord);
        // dict.add(beginWord);

        int steps = 1;
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(beginWord);
        visited.add(beginWord);

        while(!queue.isEmpty()){
            steps++;
            int size = queue.size();
            for(int i = 0; i< size; i++){
                String word = queue.poll();
                for(String next: getNextWords(word, dict)){
                    if(next.equals(endWord)){
                        return steps;
                    }

                    if(!visited.contains(next)){
                        visited.add(next);
                        queue.offer(next);
                    }
                }
            }
        }

        return 0;

    }

    public ArrayList<String> getNextWords(String word, Set<String> dict){
        ArrayList<String> result = new ArrayList<>();
        for(int i = 0; i< word.length(); i++){
            for(char c = ‘a‘; c<‘z‘; c++){
                if(word.charAt(i) == c){
                    continue;
                }

                String replaceWord = getReplacedWord(word,i,c);
                if(dict.contains(replaceWord)){
                    result.add(replaceWord);
                }
            }
        }
        
        return result;
    }
    
    public String getReplacedWord(String word, int index, char c){
        char[] chars = word.toCharArray();
        chars[index] = c;
        return new String(chars);
    }
}