N叉树的层序遍历 BFS 【 leetcode - 429 - 简单】

╰+攻爆jí腚メ 2022-03-28 12:30 139阅读 0赞

胡扯：前几天在刷DFS的题，然后把简单的题刷完后，开始准备BFS，发现BFS 和 DFS 的题都有些重复。只剩下两个题了。这个BFS的层序遍历，是个简单题，但是也写了一会，主要是之前没有这方面的经验。

## 思路： ##

1、BFS 层序遍历，一层层的遍历。我们可以把多叉树，每一层看成一个集合。（根节点，可以看成只有一个节点的集合）

2、然后我们使用递归的方法一层层去遍历。

3、第一步，就是遍历传递过来的 集合，这个集合就是这一层的全部数据了。

4、第二步，就是去找到下一层的全部节点。操作就是遍历传递过来的 集合，看看它有没有孩子节点。有就存放在一个新的集合里面。

5、第三步，下一层的节点全部遍历完成之后。把新的 集合 当作参数传递给下一层的递归。

**BFS 遍历 多叉树 代码：**

// root  在你调用这个方法的时候可以
    //    List<Node> a =  new ArrayList<Node>();
    //        a.add(root);
    //    bfs( a );
        void bfs (List<Node> root){
    
            // 第一步遍历当前层全部的节点
            for (Node r : root)
                System.out.print(r.val + " ");
            System.out.println();
            //第二步查找下一层全部的节点
            List<Node> crr = new ArrayList<>();
            for (Node r : root){
                if (r.children != null){
                    for (Node n : r.children)
                        crr.add(n);
                }
            }
            // 看下一层节点是否为0    不可以用  crr != null  因为这个  crr  已经new 出来了
            if (crr.size() > 0)
                bfs(crr);
        }

**leetcode 答案代码：**

class Solution {
    
        List<List<Integer>> arr = new ArrayList<>();
        void bfs (List<Node> root){
    
            List<Integer> aa = new ArrayList<>();
            for (Node r : root)
                aa.add(r.val);
            arr.add(aa);
            List<Node> crr = new ArrayList<>();
    
            for (Node r : root){
                if (r.children != null){
                    for (Node n : r.children)
                        crr.add(n);
                }
            }
            if (crr.size() > 0)
                bfs(crr);
        }
    
    
        public List<List<Integer>> levelOrder(Node root) {
    
            if (root == null)
                return null;
            List<Node> a =  new ArrayList<Node>();
            a.add(root);
            bfs( a );
            return arr;
        }
    
    }