leetcode429.N叉树的层序遍历

题目链接
对于一棵N叉树：

[
     [1],
     [3,2,4],
     [5,6]
]

对于一棵二叉树而言，前序中序以及后序遍历都需要使用栈这种数据结构，而对于level order traversal而言，则是一种需要使用Queue来实现广度优先的遍历算法。官方题解也标注出：

在树上使用基于队列的遍历算法，看看它的作用。这是你应该记住的一个基本算法。

首先回顾下，二叉树的层序遍历,代码如下：

import java.util.LinkedList;
import java.util.Queue;

/**
 * 按层遍历二叉树
 */
public class TraversalTree3 {

    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int value){
            this.value = value;
        }
    }

    public static void levelOrder(Node head){

        if(head != null){
            Queue<Node> queue = new LinkedList<>();
            queue.offer(head);
            while(!queue.isEmpty()){
                head = queue.poll();
                System.out.print(head.value + " ");
                if(head.left != null)
                    queue.offer(head.left);
                if(head.right != null)
                    queue.offer(head.right);
            }
        }
    }
}

对于N叉树而言，只需要在二叉树层序遍历的代码上稍作改动即可，整体思想不变。

题解：queue

代码如下：

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

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

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root != null){
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                List<Integer> tmp = new ArrayList<>();
                int size = queue.size();
                
                for(int i = 0;i < size;i++){
                    root = queue.poll();
                    tmp.add(root.val);
                    queue.addAll(root.children);
                }

                list.add(tmp);
            }
        }
        return list;
    }
}

时间复杂度：O(N)
额外空间复杂度：使用了队列这种数据结构，O(N)

执行结果: