N叉树的层序遍历_腐烂的橘子

广度优先搜索模型

Bfs(){
  //1. 建立起始步骤，队列初始化
  //2. 遍历队列中的每一种可能，
    whlie(队列不为空){
      通过队头元素带出下一步的所有可能，并且依次入队
    {
     判断当前情况是否达成目标：按照目标要求处理逻辑
    }
    继续遍历队列中的剩余情况
    }
}

N叉树的层序遍历

N叉树的层序遍历

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        //保存结果集
        List<List<Integer>> result = new LinkedList<>();
         if(root==null){
            return result;
        }
        Queue<Node> q = new LinkedList<>();//队列!
        q.offer(root);//将根节点入队
        while (!q.isEmpty()){//队列为空结束遍历!
            int size = q.size();//拿到这一层的节点个数!
            //保存这一层的节点!
            List<Integer> ret = new LinkedList<>();
            while (size-->0){//处理这一层的每一个节点!
                Node cur = q.poll();//该节点出队
                ret.add(cur.val);//保存该节点value
                for(Node x:cur.children){
                    //将这一节点的所有子节点入队!
                    q.offer(x);
                }
            }
            result.add(ret);//保存这一层节点
        }
        return result;
    }
}

腐烂的橘子

腐烂的橘子

class pair{//用来存坐标位置!
    int x;
    int y;
    public pair(int x,int y){
        this.x = x;
        this.y = y;
    }
}
class Solution {
    public int orangesRotting(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int step = 0;//记录分钟数
        //上下左右
        int[][] nextP = {{1,0},{-1,0},{0,-1},{0,1}};
        Queue<pair> q = new LinkedList<>();
        //初始化,找到第一个烂橘子位置入队!
        for(int i = 0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==2){
                    q.offer(new pair(i,j));
                }
            }
        }
        while(!q.isEmpty()){
            int size = q.size();
            boolean flag = false;//标记是否腐烂过!
            while(size-->0){
                //出队该节点!
                pair cur = q.poll();
                //处理该节点的周围方向!
                for(int i = 0;i<nextP.length;i++){
                    int x = cur.x + nextP[i][0];
                    int y = cur.y + nextP[i][1];
                    if(x>=row||x<0||y>=col||y<0){
                        //越界!
                        continue;
                    }
                    if(grid[x][y]==1){//周围是新鲜水果就腐烂!
                        grid[x][y] = 2;
                        q.offer(new pair(x,y));//入队
                        flag = true;
                    }
                }
            }
            if(flag){//这一层腐烂过!
                step++;
            }
        }
        for(int i = 0;i<row;i++){
            for(int j = 0;j<col;j++){
                if(grid[i][j]==1){//说明还有新鲜水果!
                    return -1;
                }
            }
        }
    return step;
    }
}