Formatted question description: https://leetcode.ca/all/429.html
429. N-ary Tree Level Order Traversal (Easy)
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 1.
// OJ: https://leetcode.com/problems/n-ary-tree-level-order-traversal/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
if (!root) return {};
queue<Node*> q;
q.push(root);
vector<vector<int>> ans;
while (q.size()) {
int cnt = q.size();
vector<int> level;
while (cnt--) {
root = q.front();
q.pop();
level.push_back(root->val);
for (Node *node : root->children) q.push(node);
}
ans.push_back(level);
}
return ans;
}
};
Java
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> levelOrder = new ArrayList<List<Integer>>();
if (root == null)
return levelOrder;
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> curLevel = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
curLevel.add(node.val);
List<Node> children = node.children;
if (children != null && children.size() > 0) {
int childrenCount = children.size();
for (int j = 0; j < childrenCount; j++)
queue.offer(children.get(j));
}
}
levelOrder.add(curLevel);
}
return levelOrder;
}
}