Problem
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.
Solution1: Recursion
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Running time: 44 ms class Solution { public: vector<vector<int>> levelOrder(Node* root) { vector<vector<int>> ans; preorder(root, 0, ans); return ans; } private: void preorder(Node* root, int d, vector<vector<int>>& ans) { if (root == nullptr) return; while (ans.size() <= d) ans.push_back({}); ans[d].push_back(root->val); for (auto child : root->children) preorder(child, d + 1, ans); } }; |
Solution2: Iterative
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 44 ms class Solution { public: vector<vector<int>> levelOrder(Node* root) { if (!root) return {}; vector<vector<int>> ans; queue<Node*> q; q.push(root); int depth = 0; while (!q.empty()) { int size = q.size(); ans.push_back({}); while (size--) { Node* n = q.front(); q.pop(); ans[depth].push_back(n->val); for (auto child : n->children) q.push(child); } ++depth; } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment