429.N-ary Tree Level Order Traversal #

Problem #

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]

Problem Summary #

Given an N-ary tree, return the level order traversal of its node values. (That is, traverse level by level from left to right.) The serialized input of the tree is represented using level order traversal, and each group of child nodes is separated by a null value (see examples).

Solution Approach #

• This is part of the N-ary tree series; Problem 589 is also in this series. The idea for this problem is not difficult: since it is level order traversal, solve it using BFS.

Code #

package leetcode

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

type Node struct {
	Val      int
	Children []*Node
}

func levelOrder(root *Node) [][]int {
	var res [][]int
	var temp []int
	if root == nil {
		return res
	}
	queue := []*Node{root, nil}
	for len(queue) > 1 {
		node := queue[0]
		queue = queue[1:]
		if node == nil {
			queue = append(queue, nil)
			res = append(res, temp)
			temp = []int{}
		} else {
			temp = append(temp, node.Val)
			if len(node.Children) > 0 {
				queue = append(queue, node.Children...)
			}
		}
	}
	res = append(res, temp)
	return res
}