# LC 429. N-ary Tree Level Order Traversal

### [Problem link](https://leetcode.com/problems/n-ary-tree-level-order-traversal/)

###### tags: `leedcode` `medium` `c++` `Binary Tree`

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:**

<img src="https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png" style="width: 100%; max-width: 300px;" />

Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]

**Example 2:**

<img alt="" src="https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png" style="width: 296px; height: 241px;" />

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 <code>1000</code>
- The total number of nodes is between <code>[0, 10⁴]</code>

## Solution 1
#### C++

// recursive
class Solution {
public:
    void traversal(Node *cur, vector<vector<int>> &vec, int level) {
        if (cur == nullptr) {
            return;
        }
        if (vec.size() == level) {
            vec.emplace_back(vector<int>());
        }
        vec[level].emplace_back(cur->val);
        for (Node *n: cur->children) {
            traversal(n, vec, level + 1);
        }
    }

    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        traversal(root, res, 0);
        return res;
    }
};

// iteration
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> q;
        if (root != nullptr) {
            q.push(root);
        }
        
        vector<vector<int>> res;
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;

            for (int i = 0; i < size; i++) {
                Node *node = q.front();
                q.pop();

                level.push_back(node->val);
                for (Node *child: node->children) {
                    q.push(child);
                }
            }
            res.push_back(level);
        }
        return res;
    }
};

>### Complexity
>n = number of tree's nodes.
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |

## Note
emplace_back的效率比push_back還高

push_back:
emplace_back: