429. N 叉树的层序遍历(两种解法)

---

N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

树的高度不会超过 1000
树的节点总数在 [0, 10^4] 之间

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

第一种解法：使用队列

将一层的节点都存入到队列，然后记录当前长度，一一弹出在这一长度中队列的节点，弹出的节点中，如果有节点的children不为空的，则将该节点的子节点添加到队列中，进行下一层级遍历。

public List<List<Integer>> levelOrder(Node root) {
    
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
    
        return res;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()) {
    
        int size = queue.size();
        List<Integer> cur = new ArrayList<>();
        int i = -1;
        while (++i < size) {
    
            Node node = queue.poll();
            cur.add(node.val);
            if (node.children != null) {
    
                queue.addAll(node.children);
            }
        }
        res.add(cur);
    }
    return res;
}

第二种解法：深度遍历

将当前的层数传入进方法中，如果当前的层数等于res的的长度，代表之前未访问过当前层，创建一个集合，继续递归就可以了。

 public List<List<Integer>> levelOrder(Node root) {
    
 List<List<Integer>> res = new ArrayList<>();
    dfs(root, 0, res);
    return res;
}

private void dfs(Node node, int level, List<List<Integer>> res) {
    
    if (node == null) {
    
        return;
    }
    if (res.size() == level) {
    
        res.add(new ArrayList<>());
    }
    res.get(level).add(node.val);
    if (node.children != null) {
    
        for(Node next : node.children) {
    
            dfs(next, level + 1, res);
        }
    }
}