429. N-ary Tree Level Order Traversal
Tags: ‘Tree’, ‘Breadth-first Search’
Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example, given a 3-ary tree:
We should return its level order traversal:
[
[1],
[3,2,4],
[5,6]
]
Note:
- The depth of the tree is at most
1000. - The total number of nodes is at most
5000.
Solution
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
Queue<Node> queue = new LinkedList<>();
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> tempList = new ArrayList<>();
int currentSize = queue.size();
for (int i = 0; i < currentSize; i++) {
Node curr = queue.poll();
tempList.add(curr.val);
if (curr.children != null) {
for (Node child: curr.children) {
queue.offer(child);
}
}
}
result.add(tempList);
}
return result;
}
}