沙井商城网站建设百度一下百度
✨✨ 欢迎大家来到小伞的大讲堂✨✨
🎈🎈养成好习惯，先赞后看哦~🎈🎈
所属专栏：C++_OJ
小伞的主页：xiaosan_blog
二叉树的层序遍历
102. 二叉树的层序遍历 - 力扣（LeetCode）
给你二叉树的根节点 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
解题思路：
由于树中节点数目在范围 [0, 2000] 内，空间需求量小，为了预防内部插入时，还需对空间的判断，在主函数中，开辟（2000*(int)）的空间。
vector<vector<int>> s;
s.resize(2000);
由于题目要求存放在 vector<vector<int>>二维数组中，我们需要一个变量level控制存放位置,因为resize的原因，最后我们是要释放掉没有使用的空间，所以创建size变量存放树的高度；
class Solution {
public:
void rootlevel(TreeNode* root, int level(控制存放位置), vector<vector<int>>& s,int& size(计算树的高度)(需要是全局变量或者指针变量)) {
if (root == nullptr) {
return;
}
s[level].push_back(root->val);
rootlevel(root->left, ++level, s, size);//由于左子树与右子树为同一层
rootlevel(root->right, level, s, size);//所以++level后右子树不必++
size = size >= level ? size : level;//记录树的高度
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> s;
s.resize(2000);//对于空间需求量小，提前开好空间，不必对空间进行判断
int size = 0;
rootlevel(root, 0, s, size);
s.resize(size);//释放掉不需要的空间
return s;
}
};