LC429.N叉树的层序遍历

LC429.N叉树的层序遍历 题目

查看题目

解题思路（模板题）

N叉树的层序遍历与二叉树的层序遍历在本质上没有任何区别。不同的是子树的表示方式，而叉树的子树只有左子树和右子树，N叉树的表示方式是一个节点形式的链表，因此，在普通二叉树将左右子树推入队列的部分修改成将节点链表推入队列中即可，获取节点的值使用get()函数（因为底层是数组也就是ArrayList，所以可以直接通过索引快速找到对应的值），后面的 *** 作与普通的二叉树遍历没有任何区别。

代码

// 此题用一下模板
class Solution {
    public List> levelOrder(Node root) {
        List> result = new ArrayList<>();
        Deque que = new linkedList<>();
        if (root == null) {
            return result;
        }
        que.offerLast(root);
        
        while (!que.isEmpty()) {
            List list = new ArrayList<>();
            int levelsize = que.size();
            while (levelsize > 0) {
                // 下面关于新节点的定义要在循环内部进行定义
                // 这次要判断子节点的中的节点列表的长度。
                Node node = que.peekFirst();
                que.pollFirst();
                list.add(node.val);
                int len = node.children.size();
                for (int i = 0; i < len; i++) {
                    que.offerLast(node.children.get(i));
                }
                levelsize--;
            }
            result.add(list);
            // 这里注意不要用和循环里一样的levelsize，否则会出现除0的问题
        }
        return result;

    }
}