算法
(BFS) O(n)
我们从根节点开始按宽度优先的顺序遍历整棵树,每次先扩展左儿子,再扩展右儿子。
这样我们会:
- 先扩展根节点;
- 再依次扩展根节点的左右儿子,也就是从左到右扩展第二层节点;
- 再依次从左到右扩展第三层节点;
- 依次类推
所以BFS的顺序就是这道题目要求的顺序。
时间复杂度
BFS时每个节点仅被遍历一次,所以时间复杂度是 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> printFromTopToBottom(TreeNode* root) {
vector<int> res;
if (!root) return res;
queue<TreeNode*> 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;
}
};
实际上可以简化一下,去掉三个if语句,直接在res.pushback(t−>val)前判断一下t是否为NULL,代码简单一些
/** * 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) { queue<TreeNode*> q; vector<int> r; q.push(root); while(!q.empty()){ TreeNode* f=q.front(); q.pop(); if(f!=NULL) r.push_back(f->val),q.push(f->left),q.push(f->right); } return r; } };
空节点全部进队一次,队列吞吐量翻倍。
对,但是只是因为 AC Saber 里这样方便(
好!!!
queue[HTML_REMOVED] q这句话。。。。queue是一种数据结构,后面<>里面不是应该写存放的数据类型吗,那TreeNode是一种数据结构,不是类型啊,为什么可以这么写
TreeNode也是类型。
标准的bfs层序遍历
对滴hh