leetcode--429--N叉树的层序遍历

题目：
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

例如，给定一个 3叉树 :

image.png

返回其层序遍历:

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

说明:

树的深度不会超过 1000。
树的节点总数不会超过 5000。

链接：https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal

思路：
1、采用BFS的思路，分层记录每层的节点信息，保存下来

Python代码：

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution(object):

    def __init__(self):
        self.ret = []

    def bfs(self, root):
        if not root:
            return None
        quenu = [root]
        
        while quenu:
            nex = []
            tmp = []
            for node in quenu:
                tmp.append(node.val)
                for child in node.children:
                    nex.append(child)
            quenu = nex
            self.ret.append(tmp)

    def levelOrder(self, root):
        """
        :type root: Node
        :rtype: List[List[int]]
        """
        
        self.bfs(root)

        return self.ret

C++代码：

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

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:

    vector<vector<int>> ret;

    vector<vector<int>> bfs(Node* root){
        if (root == nullptr) {
            return ret;
        }
        vector<Node*> queue;
        queue.push_back(root);

        while(queue.size()>0){
            vector<int> tmp = {};
            vector<Node*> nex = {};
            for (auto node:queue){
                tmp.push_back(node->val);
                for (auto child : node->children){
                    nex.push_back(child);
                }
            }
            ret.push_back(tmp);
            queue.swap(nex);
        }

        return ret;
    }

    vector<vector<int>> levelOrder(Node* root) {
        bfs(root);
        return ret;
    }
};