leetcode429. N 叉树的层序遍历

分析

利用层序遍历可以将每层的节点加入到队列中,问题是要控制每层的个数,可以用size变量来记录每一层有多少个节点,每当每一层最右边的点入队后,此时队的数量就是下一层节点的数量。每出队一个,size--,减为0时说明这一层结束,又将队列的数量赋给size。

/*
// 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:
    queue<Node*> q;
    vector<vector<int>> ans;
    vector<int> cur;
    vector<vector<int>> levelOrder(Node* root) {
        if(!root)return ans;
        q.push(root);
        int size=1;
        while(q.size()){
            auto t = q.front();
            q.pop();
            cur.push_back(t->val);
            for(auto cc:t->children){
                    q.push(cc);
                }
            --size;
            if(size==0){
                size=q.size();
                ans.push_back(cur);
                cur.clear();
            }
        }
        return ans;
    }
};