Contents

# 429. 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 :

Note

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

#### 解題思路 :

• 這題是level order traversal的變化題，一樣可以用queue來解決，可以參考 leetcode102題解
• 從leetcode102題的判斷left children & right children 改成一整個Children array就可以摟!!

### Queue解法

• if time comlexity of golang built-in function append() is O(1) , time complexity: O(n) , space complexity: O(n)

Runtime: 0 ms, faster than 100.00% of Go online submissions for N-ary Tree Level Order Traversal.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 `````` ``````/** * Definition for a Node. * type Node struct { * Val int * Children []*Node * } */ func levelOrder(root *Node) [][]int { var res [][]int if root == nil { return res } var queue []*Node queue = append(queue, root) for len(queue) != 0 { length := len(queue) tempArr := make([]int, 0) for i := 0; i < length; i++ { node := queue[0] tempArr = append(tempArr, node.Val) if len(node.Children) != 0 { queue = append(queue, node.Children...) } queue = queue[1:] } res = append(res, tempArr) } return res } ``````