Java描述 LeetCode，429.N-ary Tree Level Order Traversal N叉树的层次遍历

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。

Given an n-ary tree, return the level order traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]

Example 2:

Input: 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]
Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

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

☘️利用层次遍历层次遍历代码的模板代码，只需要将左右子树的判断换成孩子就可以啦。

static class Node {
    public int val;
    public List children;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List _children) {
        val = _val;
        children = _children;
    }
}




public List> levelOrder(Node root) {
    List> naryLevelOrder = new ArrayList<>();
    Queue queue = new ArrayDeque<>();

    if (root == null) {
        return naryLevelOrder;
    }

    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List levelNodes = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            if (!node.children.isEmpty()) {
                queue.addAll(node.children);
//                    for (Node n : node.children) {
//                        queue.offer(n);
//                    }
            }
            levelNodes.add(node.val);
        }
        naryLevelOrder.add(levelNodes);
    }
    return naryLevelOrder;
}

☘️二叉树的层次遍历中，还有一种深度优先算法，在这里我们也是完全可以用滴

public static void dfs(Node root, int level, List> levelNodes) {
    if (root == null) {
        return;
    }
    if (levelNodes.size() == level) {
        levelNodes.add(new ArrayList<>());
    }
    levelNodes.get(level).add(root.val);
    for (Node node : root.children) {
        dfs(node, level + 1, levelNodes);
    }
}


public List> levelOrder3(Node root) {
    List> naryLevelOrder = new ArrayList<>();

    if (root == null) {
        return naryLevelOrder;
    }
    int initialLevel = 0;
    dfs(root, initialLevel, naryLevelOrder);
    return naryLevelOrder;
}

☘️这个题目还是很简单的，只要会层次遍历，n叉树是一样的。