文章目录
零、原题链接
一、题目描述
给你二叉树的根节点 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
)
\Omicron(n)
O(n)
空间复杂度：
O
(
n
)
\Omicron(n)
O(n)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root)
return {};
vector<vector<int>> ans;
queue<TreeNode*> bfs;
bfs.push(root);
while (bfs.size()) {
ans.push_back(vector<int>());
for (int i = bfs.size(); i > 0; i--) {
if (bfs.front()->left)
bfs.push(bfs.front()->left);
if (bfs.front()->right)
bfs.push(bfs.front()->right);
ans.back().push_back(bfs.front()->val);
bfs.pop();
}
}
return ans;
}
};