1. 问题描述
给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。
树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。
提示:
树的高度不会超过 1000
树的节点总数在 [0, 10^4] 之间
2. 思路
依旧是模板题目,只不过一个节点有多个孩子了。
注意把当前节点的孩子节点压入队列时,与二叉树的区别
3.代码
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func levelOrder(root *Node) [][]int {
var res [][]int
if root == nil {
return res
}
queue := []*Node{root}
for len(queue) > 0 {
length := len(queue)
var layer []int
for i := 0; i < length; i++ {
// 把当前节点的Children全部压入队列
for j := 0; j < len(queue[0].Children); j++ {
if queue[0].Children[j] != nil {
queue = append(queue, queue[0].Children[j])
}
}
layer = append(layer, queue[0].Val)
queue = queue[1:]
}
res = append(res, layer)
}
return res
}