Leetcode 429. N-ary Tree Level Order Traversal

[medium]

N-ary Tree Level Order Traversal - LeetCode

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]

[Java]

Think: use queue like BST to scan Node level by level

Trick: use LinkedList to offer the new node val

1. create List<List<Integer>> for the result
2. if root == null, return result
3. create Queue<Node> queue as LinkedList, offer the root in queue
4. while queue is not empty, create another new list, poll all the node in queue, add them into the current list, at the same time, add node.children into the queue -> first in first out -> so we have to know queue size in the first place
5. result add current list and check it again until queue is empty
6. return result