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

剑指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/