N 叉树的层序遍历

方法一:广度优先搜索思路与算法

对于「层序遍历」的题目,我们一般使用广度优先搜索。在广度优先搜索的每一轮中,我们会遍历同一层的所有节点。

具体地,我们首先把根节点 root 放入队列中,随后在广度优先搜索的每一轮中,我们首先记录下当前队列中包含的节点个数(记为 cnt),即表示上一层的节点个数。在这之后,我们从队列中依次取出节点,直到取出了上一层的全部 cnt 个节点为止。当取出节点 cur 时,我们将 cur 的值放入一个临时列表,再将 cur 的所有子节点全部放入队列中。

当这一轮遍历完成后,临时列表中就存放了当前层所有节点的值。这样一来,当整个广度优先搜索完成后,我们就可以得到层序遍历的结果。

class Node {
public:
    int val;
    vector<Node*> children;
};

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        if (!root) {
            return {};
        }

        vector<vector<int>> ans;
        queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            int cnt = q.size();
            vector<int> level;
            for (int i = 0; i < cnt; ++i) {
                Node* cur = q.front();
                q.pop();
                level.push_back(cur->val);
                for (Node* child: cur->children) {
                    q.push(child);
                }
            }
            ans.push_back(move(level));
        }

        return ans;
    }
};
    

复杂度分析

时间复杂度:O(n),其中 n 是树中包含的节点个数。在广度优先搜索的过程中,我们需要遍历每一个节点恰好一次。

空间复杂度:O(n),即为队列需要使用的空间。在最坏的情况下,树只有两层,且最后一层有 n−1 个节点,此时就需要 O(n) 的空间。

全部评论

相关推荐

面向对象的火龙果很爱...:去吃一顿炸鸡就走
点赞 评论 收藏
分享
05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务