###### tags: `LeetCode` `Medium` `Tree` `BFS` `DFS` `Queue`
# LeetCode #429 [N-ary Tree Level Order Traversal](https://leetcode.com/problems/n-ary-tree-level-order-traversal/)
### (Medium)
給定一個 N 元樹，返回其節點值的層序遍歷。 （即從左到右，逐層遍歷）。

樹的序列化輸入是用層序遍歷，每組子節點都由 null 值分隔（參見示例）。

---
BFS(廣度優先) :
利用佇列(queue)特性, 一輪處理一個階層的所有節點, 同時將該節點的子節點插入佇列中, 而由於這一輪需要做的處理次數已經決定了, 所以可以清楚的分辨插入的節點應為第幾層。

要注意每一輪開始前須在答案數組中插入一個新的位置。

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        if(root==nullptr)return {};
        vector<vector<int>> nodes;
        queue<Node*> q;
        q.push(root);
        while(!q.empty()){
            nodes.emplace_back();
            for(int i=q.size();i>0;i--){
                Node* curr=q.front();q.pop();
                nodes.back().push_back(curr->val);
                for(Node* child:curr->children){
                    q.push(child);
                }
            }
        }
        return nodes;
    }
};

---
DFS(深度優先) :
由於不像BFS有辦法一次處理完一輪, 所以在插入節點值到答案數組時需要知道要插入哪一層數組, 因此插入函式的參數除了節點外還要有整數表示該節點的層數。

一樣注意, 當答案數組的大小等於層數時, 代表該節點為該層數的第一個插入節點, 此時要為答案數組新增一層以避免溢位。(0~n-1總共n層)

class Solution {
public:
    vector<vector<int>> nodes;
    vector<vector<int>> levelOrder(Node* root) {
        if(root){
            dfs(root,0);
            return nodes;
        }
        return {};
    }
    void dfs(Node* root, int level){
        if(root==nullptr)return;
        if(level==nodes.size())nodes.emplace_back();
        nodes[level].push_back(root->val);
        for(auto c:root->children){
            dfs(c,level+1);   
        }
    }
};