102. 二叉树的层序遍历
难度中等1411
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
代码语言：javascript复制输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]示例 2：
代码语言：javascript复制输入：root = [1]
输出：[[1]]示例 3：
代码语言：javascript复制输入：root = []
输出：[]提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
思路：
说到层序遍历，就想到广度优先遍历以及队列hhh！
但是这道题不太一样的是，它要求要按一个数组的形式返回，也就是说把每一层的元素放到一个一维数组，再把这些一维数组放到一个二维数组中去，所以我们得控制它遍历每层的元素个数，另外，还可以借助vector来存储（睁眼说瞎话，题目要求返回 “二维vector” 哈哈哈）。
步骤：
- 创建一个 “二维vector” vv 和 一个队列 q，并判断一下 root 是否为空，若不为空则将其入队。
- 通过 n 来统计每次 队列q 中的个数，也就是每层元素的个数，然后进行 n 次循环。
- 在子循环中，每次将该层元素放到新的 “一维vector” v 中去，然后判断该节点是否有左右孩子，有的话就将其入队列。
- 接着将 v 尾插到 vv 中去，一直循环，直到队列q 为空则结束。
- 最后返回 vv。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> vv;
queue<TreeNode*> q;
//防止空指针
if(root != nullptr)
{
q.push(root);
}
while(!q.empty())
{
int n = q.size();
vector<int> v;//用一个一维vector来存该层的数值
for(size_t i = 0; i < n; i )
{
TreeNode* tmp = q.front();
q.pop();
v.push_back(tmp->val);
if(tmp->left)
{
q.push(tmp->left);
}
if(tmp->right)
{
q.push(tmp->right);
}
}
//记得把该层的一维vector尾插到vv中去
vv.push_back(v);
}
return vv;
}
};107. 二叉树的层序遍历 II
难度中等602
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
代码语言：javascript复制输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]示例 2：
代码语言：javascript复制输入：root = [1]
输出：[[1]]示例 3：
代码语言：javascript复制输入：root = []
输出：[]提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
思路：
有了上面第一题，这道题就很简单了！
刚开始想，是不是觉得很难？但是仔细一想，其实就是将我们第一题最后的 vv 逆序一下，就变成了自底向上的顺序了！
我们可以借助函数 reverse 替我们完成！
代码语言：javascript复制class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> vv;
queue<TreeNode*> q;
if(root != nullptr)
q.push(root);
while(!q.empty())
{
int n = q.size();
vector<int> v;
for(size_t i = 0; i < n; i)
{
TreeNode* tmp = q.front();
q.pop();
v.push_back(tmp->val);
if(tmp->left)
q.push(tmp->left);
if(tmp->right)
q.push(tmp->right);
}
vv.push_back(v);
}
//上面的操作都是一致的，只需要最后逆序一下即可！
reverse(vv.begin(), vv.end());
return vv;
}
};
