题目

点击前往

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

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

示例 1：

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

解题思路

  • 这里解题思路与二叉树的层序遍历一样，我们只需要注意N叉树的存储结构就可以很轻松的完成遍历。

  • 针对示例中的N叉树存储结构如下：

所以我们每次只需要访问其children，如果不为null，则将它们拼接起来，然后返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    let queue =[], result =[];
    if(root === null) return result;
    console.log(root);
    queue.push(root);
    while(queue.length !==0){
        let len = queue.length;
        let curLevel =[];
        for(let i=0;i<len;i++){
            let node = queue.shift();
            curLevel.push(node.val);
            if(node.children)
                queue = queue.concat(node.children);
        }
        result.push(curLevel);
    }
    return result;
};