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

本文主要是介绍剑指offer：分行从上往下打印二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- - 分析
  - 题目来源

分析

在这里插入图片描述

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

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

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

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vector<vector<int>> printFromTopToBottom(TreeNode* root) {vector<vector<int>> res;if (root == nullptr) return res;queue<TreeNode*> q;q.push(root);q.push(nullptr);vector<int> level;while (q.size()) {auto t = q.front();q.pop();// 正常bfsif(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;}
};