N叉树的层序遍历-BFS

孙泽辉

发布于：2021年8月30日

字数：413字

时长：1分钟

次浏览

昨天晚上睡不着，想到了层序遍历，有点像BFS，没想到真的是用BFS

课本上给出了二叉树的层序遍历，去LeetCode上搜到了N叉树的，应该是差不多的。

题目

429. 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]]

题解

要返回二维数组，并且一个根节点底下可能有N个子节点，照课本上二叉树的写法肯定是不行拉。

这里使用数组模拟Queue，按照BFS（广度优先搜索）的思想，将每一层的节点放入数组里。

/**
 * Definition for node.
 * class Node {
 *     val: number
 *     children: Node[]
 *     constructor(val?: number) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.children = []
 *     }
 * }
 */
function levelOrder(root: Node | null): number[][] {
  if (!root) return [];
  const q: Array<Node> = [root];
  const ret: Array<Array<number>> = [];
  while (q.length !== 0) {
    const temp: Array<number> = [];
    const qlen = q.length;
    for (let i = 0; i < qlen; i++) {
      const vertex = q.shift();
      temp.push(vertex.val);
      q.push(...vertex.children);
    }
    ret.push(temp);
  }
}

复杂度分析

• 时间复杂度：O(n)O(n)。nn 指的是节点的数量。
• 空间复杂度：O(n)O(n)。

题目地址：

429. N 叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)