LeetCode每日一题(N-ary Tree Level Order Traversal)

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]

}