73-N叉树的层序遍历

自己的做法

算法思想

使用层次遍历算法，用到数据结构队列queue。

遍历每一层时，需要确定该层是否遍历结束。则需要设置一个标志变量last，初始指向根节点， 遍历节点时，判断该节点与last是否相等。

若相等，则代表该层已遍历完毕，若queue不为空，则队尾元素为下一层的末尾节点，将last指向该节点；

若不相等，则正常执行。

把每一层节点值存入数组中即可。

注：此题childen类型是数组，因此可直接使用数组长度来判断是否到末尾节点。

算法实现

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) {

        vector<vector<int>> res;
        if(root == nullptr) {
            return res;
        }
        // 指向每一层末尾节点
        Node * last = root;
        // 遍历树
        Node * p = nullptr;
        queue<Node *> q;
        q.push(root);

        while (!q.empty()) {
            vector<int> tmp;
            // 判断遍历节点与末尾节点是否相等
            while(p != last) {
                p = q.front();
                q.pop();
                tmp.push_back(p->val);
                for(int i = 0; i < p->children.size(); i++) {
                    q.push(p->children[i]);
                }
            }
            // 修改末尾节点指向
            last = q.back();
            res.push_back(tmp);
        }
        
		return res;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(n)$。