算法
(BFS) O(n)
宽度优先遍历，一层一层来做。即：
- 将根节点插入队列中；
- 创建一个新队列，用来按顺序保存下一层的所有子节点；
- 对于当前队列中的所有节点，按顺序依次将儿子加入新队列，并将当前节点的值记录在答案中；
- 重复步骤2-3，直到队列为空为止。
时间复杂度
树中每个节点仅会进队出队一次，所以时间复杂度是 O(n)。
C++ 代码
/**
* 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> get_val(vector<TreeNode*> level)
{
vector<int> res;
for (auto &u : level)
res.push_back(u->val);
return res;
}
vector<vector<int>> printFromTopToBottom(TreeNode* root) {
vector<vector<int>>res;
if (!root) return res;
vector<TreeNode*>level;
level.push_back(root);
res.push_back(get_val(level));
while (true)
{
vector<TreeNode*> newLevel;
for (auto &u : level)
{
if (u->left) newLevel.push_back(u->left);
if (u->right) newLevel.push_back(u->right);
}
if (newLevel.size())
{
res.push_back(get_val(newLevel));
level = newLevel;
}
else break;
}
return res;
}
};
/** * 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) return res; queue<TreeNode*> q; q.push(root); while (q.size()) { vector<int> lv; int sz = q.size(); while (sz--) { auto t = q.front(); q.pop(); lv.push_back(t->val); if (t->left) q.push(t->left); if (t->right) q.push(t->right); } res.push_back(lv); } return res; } };写完发现跟楼下大佬一样，我觉得有些题还是自己先写写，也不错，不用一直跟Y总一模一样
class Solution { public: vector<vector<int>> ans; vector<int> path; vector<vector<int>> printFromTopToBottom(TreeNode* root) { if (!root) return ans; queue<TreeNode*> q; q.push(root); while (q.size()) { // 或者这里写while(1)， 然后里面末尾写if(队列空)break; int level_node_cnt = q.size(); // 当前层的非空节点个数 while (level_node_cnt -- ) { // 每取一个节点，就减一，用了一个当前层咯 // 取队头结点 TreeNode* t = q.front(); q.pop(); if (t->left) q.push(t->left); if (t->right) q.push(t->right); // 当前层放进去 path.push_back(t->val); } // 当前层非空结点都遍历好了，丢进答案 ans.push_back(path); path.clear(); // 清空，下一层用 } return ans; } };