【二叉树】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;}
};