102. 二叉树的层序遍历
一句话套路BFS 按层出队,用 size 定层宽
题目描述
给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1] 输出:[[1]]
示例 3:
输入:root = [] 输出:[]
提示:
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
思路
时间
O(n)空间
O(最宽一层) = O(n)思路
BFS + 「进入循环前先记下 q.size()」,这个 size 就是当前层的结点数,于是天然把层与层分开。Q199 右视图 / Q103 锯齿 / Q107 自底向上都改这一行。
图解
二叉树(来自本仓库测试数据,
nullopt 表示空位)逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0102 {
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int sz = (int)q.size(); // 本层结点数,关键一步
ans.emplace_back();
ans.back().reserve(sz);
for (int i = 0; i < sz; ++i) {
TreeNode* cur = q.front();
q.pop();
ans.back().push_back(cur->val);
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}
return ans;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0102::Solution s;
TreeNode* a = buildTree({3, 9, 20, nullopt, nullopt, 15, 7});
CHECK_EQ(s.levelOrder(a), vector<vector<int>>({{3}, {9, 20}, {15, 7}}));
freeTree(a);
CHECK_EQ(s.levelOrder(nullptr), vector<vector<int>>{});
TreeNode* b = buildTree({1});
CHECK_EQ(s.levelOrder(b), vector<vector<int>>({{1}}));
freeTree(b);