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

提示：

• 树的高度不会超过 1000
• 树的节点总数在 [0, 10^4] 之间4

---

解题分析及思路：

N叉树的遍历类似于二叉树的遍历，不熟悉二叉树的遍历可以查看二叉树。

参考二叉树的层序遍历，我们可以使用队列进行层序遍历，同时使用两个指针 index 和 l 来维护每一层的起点和终点。

遍历时，将每一层的节点值加入结果集中，并将该层所有节点的子节点依次加入队列中，以保证下一轮遍历按照从左至右的顺序输出节点。

1. 使用一个切片 queue 来模拟队列，初始时将根节点加入队列。
2. 使用指针 index 表示当前层的起点下标，l 表示当前层的终点下标。
3. 在遍历每一层时，将该层所有节点值加入结果集，同时将该层所有节点的子节点加入队列，更新 l 值。

func levelOrder(root *Node) (result [][]int) {
	if root == nil {
		return
	}
	queue := make([]*Node, 0)
	queue = append(queue, root)
	index := 0
	l := len(queue)
	for len(queue) != index {
		var row = make([]int, 0)
		for ; index < l; index++ {
			row = append(row, queue[index].Val)
			queue = append(queue, queue[index].Children...)
		}
		l = len(queue)
		result = append(result, row)
	}
	return
}

复杂度：

• 时间复杂度：O(N)，其中 N 为 n 叉树中节点的数量，因为每个节点都只会被访问一次。
• 空间复杂度：O(N)，其中 N 为 n 叉树中节点的数量。

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:4.2 MB,击败了71.25% 的Go用户