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; } }
-
// 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 {}; vector<vector<int>> ans; queue<Node*> q{ {root} }; while (q.size()) { int cnt = q.size(); vector<int> level; while (cnt--) { auto node = q.front(); q.pop(); level.push_back(node->val); for (auto &child : node->children) q.push(child); } ans.push_back(level); } return ans; } };
-
""" # Definition for a Node. class Node(object): def __init__(self, val, children): self.val = val self.children = children """ class Solution(object): def levelOrder(self, root): """ :type root: Node :rtype: List[List[int]] """ if not root: return [] queue = [(root, 0)] res = [[]] while queue: node, level = queue.pop(0) if level >= len(res): res.append([]) res[level].append(node.val) for child in node.children: queue.append((child, level + 1)) return res