【二叉树】Leetcode N 叉树的层序遍历

题目讲解

429. N 叉树的层序遍历

算法讲解

在做层序遍历的时候由于它的每一个结点是有val + vector child组成，所以在做层序遍历的时候需要考虑它每一层结点的个数，那我们就可以使用一个queue保存每一层的结点；那么我们在做第一层的时候，这样很简单，第一层用完怎么做呢？我们在准备第二层结点的时候，就需要将第一层结点提取出来，然后将第一层节点pop出去，现在的时候，第一层的vector ret已经出现的，但是我们queue还是没有处理的，所以在添加当前节点的val之后就需要遍历结点的child vector，将它的下一层结点放到queue中，这样的话，每一层的结点就会出现在queue中

/*
// 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>> levelOrder(Node* root) {
        int levesize = 0;
        queue<Node*>q;
        vector<vector<int>>ret;
        if(root == nullptr)return ret;
        q.push(root);
        while(!q.empty())
        {
            levesize = q.size();
            vector<int> temp;
            for(int i = 0; i < levesize; i++)
            {
                Node* cur = q.front();
                q.pop();
                temp.push_back(cur->val);
                for(Node* child : cur->children)
                {
                    q.push(child);
                }
            }
            ret.push_back(temp);
        }
        return ret;
    }
};