题目描述
从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。
数据范围
树中节点的数量 [0,1000]。
样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null] 8 / \ 12 2 / 6 / 4 输出：[8, 12, 2, 6, 4]
方法一：BFS O(n)
这道题的要求是需要我们按层来输出结点，那么可以用 BFS 来做：
先判断根结点是否为空，如果不为空则推入队列。
根据队列中结点的个数来作为每次循环的条件。
每次将推出的结点的值放入答案，并判断其左右结点是否为空，不为空的话推入对应结点。
我们举一个例子，来看看是如何实现的，假设我们要遍历这棵树：
初始化： 先将根结点推入队列。
第一轮遍历：k = 1 ，更新 ans 数组并往队列推入弹出元素的孩子结点。
第二轮遍历：k = 2 ，更新 ans 数组并往队列推入弹出元素的孩子结点。
第三轮遍历：k = 4 ，更新 ans 数组并往队列推入弹出元素的孩子结点，发现已经没有可以推入的结点，直接返回 ans 数组即可。
/** * 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<int> printFromTopToBottom(TreeNode* root) { if (!root) return {}; queue<TreeNode*> q; q.push(root); vector<int> ans; while (!q.empty()) { int k = q.size(); while (k--) { auto t = q.front(); ans.push_back(t->val); q.pop(); if (t->left != NULL) q.push(t->left); if (t->right != NULL) q.push(t->right); } } return ans; } };
欢迎大家在评论区交流~
