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

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

文章目录

• • • 分析
    • 来源

分析

思路

典型的bfs模板题，这里使用STL中的queue，没用数组模拟队列。
STL的思路：初始化队列时，根root入队；对于bfs主体过程while循环内，取队头元素，队头元素出队，下一层元素入队。当然，中间需要把元素存储vector中。

时间复杂度:O(n)，每个元素遍历一遍

class Solution {
public:
    vector printFromTopToBottom(TreeNode* root) {
        vector res;
        if (root == nullptr) return res;
        queue q;
        q.push(root);
        while (q.size()) {
            auto t = q.front();
            q.pop();
            res.push_back(t->val);
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
        }
        return res;
    }
};

来源

https://www.acwing.com/problem/content/description/41/