Given an n-ary tree, return the level order traversal of its nodes’ values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Example 1:
Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]
Example 2:
Input: 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]
Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
Constraints:
- The height of the n-ary tree is less than or equal to 1000
- The total number of nodes is between [0, 104]
说句题外话, 这题跟 Nary-Tree input serialization 貌似没有啥关系啊， 提到这莫非是单纯为了让我们涨涨知识?
我感觉这题起这么长的名字完全就是为了迷惑我们，当然也可能让我们了解一下这种遍历方法和序列化的表示方式。其实整了这么多专有名词，三个字母就可以把这题表达清楚了—BFS。
代码实现(Go):
func traversal(nodes []*Node, level int, ans [][]int, maxLevel *int) {
*maxLevel = level
nexts := make([]*Node, 0, 1000)
for _, node := range nodes {
ans[level] = append(ans[level], node.Val)
nexts = append(nexts, node.Children...)
}
if len(nexts) == 0 {
return
}
traversal(nexts, level+1, ans, maxLevel)
}
func levelOrder(root *Node) [][]int {
if root == nil {
return nil
}
ans := make([][]int, 1000)
nodes := []*Node{root}
maxLevel := 0
traversal(nodes, 0, ans, &maxLevel)
return ans[:maxLevel+1]
}