429-n-ary-tree-level-order-traversal.md

429. N-ary Tree Level Order Traversal - N叉树的层序遍历

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

例如，给定一个 3叉树 :

 

 

返回其层序遍历:

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

 

说明:

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

---

题目标签：Tree / Breadth-first Search

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	60 ms	N/A

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

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        if(!root){
            return res;
        }
        queue<Node*> seq;
        set<Node*> vt;
        vt.insert(root);
        seq.push(root);
        vector<int> row;
        row.push_back(root->val);
        res.push_back(row);
        while(!seq.empty()){
            int n = seq.size();
            vector<int> row;
            while(n--){
                Node* tmp = seq.front();
                seq.pop();
                for(Node* child : tmp->children){
                    if(!vt.count(child)){
                        vt.insert(child);
                        seq.push(child);
                        row.push_back(child->val);
                    }
                }
            }
            if(!row.empty()){
                res.push_back(row);
            }
        }
        return res;
    }
};