剑指offer:分行从上往下打印二叉树

剑指offer:分行从上往下打印二叉树,第1张

剑指offer:分行从上往下打印二叉树

文章目录
      • 分析
      • 题目来源

分析

思路:
在原来bfs的基础上,每一层结束时做一个标记nullptr,每当扫描到这个标记时,就将当前队列中元素存入vector中,并清空队列,进入下一层。

这里加标记需要注意的是,当遍历到最后一层时,不用加标记。遍历完最后一层时,queue为空,所以这句代码这样写:if (q.size()) q.push(nullptr);// q不空再加标签nullptr

时间复杂度:O(n),每个元素遍历一遍
ac代码

class Solution {
public:
    vector> printFromTopToBottom(TreeNode* root) {
        vector> res;
        if (root == nullptr) return res;
        queue q;
        q.push(root);
        q.push(nullptr);
        vector level;
        
        while (q.size()) {
            auto t = q.front();
            q.pop();
            // 正常bfs
            if(t != nullptr) {
                level.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            // 遇到标记
            else {
                res.push_back(level); // 一行存入vector中
                level.clear();
                // 这里之所以要判断一下queue不空
                // 是因为bfs遍历每一层,都会把下一层结点压入队列中
                // 如果队列为空,则说明已经是最后一层,无需再加标记
                if (q.size()) q.push(nullptr);
            }
        }
        return res;
    }
};
题目来源

https://www.acwing.com/problem/content/42/

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5693660.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存