leetcode hot100刷题日记——33.二叉树的层序遍历

题目描述

解答：用队列
思路都差不多，我觉得对于我自己来说，此题最大的难点在于二维vector的初始化。

和之前有行数的初始化不一样的是：此题不确定行数，也不确定列数。

那我们就以此题为例，总结一下二维vector的初始化吧。

情况1：不确定行数和列数

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {//用队列啦（先进先出）//每一层节点都进队列完，再开始一个一个出队列//出来的队头元素继续看有没有左右孩子节点，有的话进队列，没有的话那就不管了vector<vector<int>>res;if(!root){return res;}queue<TreeNode*>q;q.push(root);while(!q.empty()){int curLevelsize=q.size();//记录当前层有的节点个数//vector<int>()创建一个空的vector<int>对象。push_back将这个空的vector<int>添加到res的末尾。每次调用该语句时，都会为新的一层创建一个空的vector<int>，用于存放该层的节点值res.push_back(vector<int>());for(int i=0;i<curLevelsize;i++){TreeNode *node=q.front();q.pop();//res.back()获取res中最后一个vector<int>（即当前层的存储容器）。push_back(node->val)将当前节点的值添加到该vector<int>的末尾。res.back().push_back(node->val);if(node->left){q.push(node->left);}if(node->right){q.push(node->right);}}}return res;}
};

定义：vector<vector>res;
初始化新的行并且先插进vector中：res.push_back(vector());
在新的行中一个一个添加数：res.back().push_back(node->val);

vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if (!root) return res;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int curLevelSize = q.size();res.emplace_back(); // 直接在res末尾构造一个空的vector<int>for (int i = 0; i < curLevelSize; i++) {TreeNode* node = q.front();q.pop();res.back().push_back(node->val); // 添加到最后一层的vector中if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return res;
}

定义：vector<vector> res;
初始化新的行并且先插进vector中：res.emplace_back();
再在新的行中一个一个添加数：res.back().push_back(node->val);
（此法效率比上一个高些）

vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if (!root) return res;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int curLevelSize = q.size();vector<int> level(curLevelSize); // 预留当前层的空间大小for (int i = 0; i < curLevelSize; i++) {TreeNode* node = q.front();q.pop();level[i] = node->val; // 直接赋值if (node->left) q.push(node->left);if (node->right) q.push(node->right);}res.push_back(level); // 将当前层的vector整体添加到res中}return res;
}

定义：vector<vector> res;
先单独初始化行：vector level(curLevelSize);
再把整行插入vector：res.push_back(level);
(个人感觉此方法最好记)

情况2：已知行数和列数

int rows = 3;
int cols = 4;
vector<vector<int>> res(rows, vector<int>(cols));res[i][j] = value;  // 直接为第 i 行第 j 列赋值

情况3：已知行数但不知道列数

int rows = 5;
vector<vector<int>> res(rows);vector<int> temp = {1, 2, 3};
res[i] = temp;  // 将第 i 行设置为新行
res[i].push_back(4);  // 在第 i 行中添加元素4

情况4：已知列数但不知道行数

int cols = 4;
vector<vector<int>> res;vector<int> row(cols);
res.push_back(row);  // 添加一行，每行有cols个默认初始化的元素