429N叉树的层序遍历.md

题目描述

https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

例如，给定一个 3叉树 :

返回其层序遍历：

[
    [1],
    [3,2,4],
    [5,6]
]

说明：

1. 树的深度不会超过 1000。

• 树的节点总不会超过 5000。

---

思路一

广度优先搜索，层序遍历，递归实现

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        layer.clear();
        if( !root ) return layer;
        
        q.push(root);
        temp.push_back(root->val);
        layer.push_back(temp);
        
        bfs();
        return layer;
    }

private:
    vector<vector<int>> layer;
    vector<int> temp;
    queue<Node*> q;
    
    void bfs(){
        temp.clear();
        int len = q.size();
        
        for(int i=0; i<len; i++){
            
            if( !q.front()->children.empty() ){
                
                int n = q.front()->children.size();
                for(int j=0; j<n; j++){
                    q.push(q.front()->children[j]);
                    temp.push_back(q.front()->children[j]->val);
                }
            }
            
            q.pop();
        }
        
        if( temp.empty() ) return;
        else{
            layer.push_back(temp);
            bfs();
        }
    }
};