BM26. 求二叉树的层序遍历
描述
给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
示例1
输入:
{1,2}
输出:
[[1],[2]]
示例2
输入:
{1,2,3,4,#,#,5}
输出:
[[1],[2,3],[4,5]]
C++ 解法, 执行用时: 42ms, 内存消耗: 11632KB, 提交时间: 2022-04-01
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
static const auto io_sync_off = []{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrder(TreeNode* root) {
// write code here
queue<TreeNode* > q;
TreeNode* tmp;
vector<vector<int > > res;
vector<int > temp;
if(root == nullptr)
return res;
q.push(root);
q.push(NULL);
while(!q.empty()){
tmp = q.front();
q.pop();
if(tmp){
temp.push_back(tmp->val);
if(tmp->left)
q.push(tmp->left);
if(tmp->right)
q.push(tmp->right);
}else{
res.push_back(temp);
temp.clear();
if(q.size())
q.push(NULL);
}
}
return res;
}
};
//用队列搞定
C 解法, 执行用时: 44ms, 内存消耗: 10788KB, 提交时间: 2022-06-22
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型二维数组
* @return int* returnSize 返回数组行数
* @return int** returnColumnSizes 返回数组列数
*/
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes ) {
// write code here
*returnSize = 0; //空树
if(root == NULL){
return NULL;
}
struct TreeNode* queue[100000]; //新建队列
int** res = (int**)malloc(sizeof(int*) * 100000); //返回数组的行数，即数有多少层
*returnColumnSizes = (int*)malloc(sizeof(int) * 100000); //数组的列数，即每层多少元素
int head = 0,rear = 0; //队列的头尾指针
queue[rear] = root; //根节点入队
rear++; //尾指针向后移动一位
while(head != rear){ //只要队列非空就一直执行
int curRear = rear; //记录当前层的尾节点
int k = 0; //记录当前层的节点个数
res[*returnSize] = (int*)malloc(sizeof(int) * (curRear - head)); //返回当前层数组元素个数
while(head < curRear){ //遍历当前层的节点
struct TreeNode* p = queue[head]; //队头元素出队
res[*returnSize][k++] = p->val; //更新返回数组中的值
if(p->left != NULL){ //将当前出队元素的左孩子节点入队
queue[rear++] = p->left;
}
if(p->right != NULL){ //将当前出队元素的右孩子节点入队
queue[rear++] = p->right;
}
head++; //队头指针向后移动一位
}
(*returnColumnSizes)[*returnSize] = k; //更新返回数组本层节点个数
(*returnSize)++; //指针指向下一层返回数组
}
return res;
}
C++ 解法, 执行用时: 44ms, 内存消耗: 11632KB, 提交时间: 2022-07-04
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
static const auto io_sync_off = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (root == nullptr)
{
return res;
}
queue<TreeNode*> q;
q.push(root);
TreeNode* cur;
while (!q.empty())
{
vector<int> row;
int n = q.size();
for (int i = 0; i < n; i++)
{
cur = q.front();
q.pop();
row.push_back(cur->val);
if (cur->left)
{
q.push(cur->left);
}
if (cur->right)
{
q.push(cur->right);
}
}
res.push_back(std::move(row));
}
return res;
}
};
C++ 解法, 执行用时: 45ms, 内存消耗: 11652KB, 提交时间: 2022-05-21
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
static const auto io_sync_off = []
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrder(TreeNode* root) {
// write code here
queue<TreeNode* > q;
TreeNode* tmp;
vector<vector<int > > res;
vector<int > temp;
if(root == nullptr)
return res;
q.push(root);
q.push(NULL);
while(!q.empty()){
tmp = q.front();
q.pop();
if(tmp){
temp.push_back(tmp->val);
if(tmp->left)
q.push(tmp->left);
if(tmp->right)
q.push(tmp->right);
}else{
res.push_back(temp);
temp.clear();
if(q.size())
q.push(NULL);
}
}
return res;
}
};
C 解法, 执行用时: 46ms, 内存消耗: 10804KB, 提交时间: 2022-04-16
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*
* C语言声明定义全局变量请加上static，防止重复定义
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型二维数组
* @return int* returnSize 返回数组行数
* @return int** returnColumnSizes 返回数组列数
*/
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes ) {
// write code here
*returnSize = 0;
if(root == NULL){
** returnColumnSizes = NULL;
return NULL;
}
int **a = (int **)malloc(sizeof(int *) * 100000);
*returnColumnSizes = (int *)malloc(sizeof(int) * 100000);
//引入队列
struct TreeNode *queue[100000];
int begin = 0, size = 1;
int end = size;
queue[0] = root;
while(begin < size) {
int colsize = end - begin;
(*returnColumnSizes)[(*returnSize)] = colsize;
int *temp = (int *)malloc(sizeof(int) * colsize);
for(int i = begin; i < end; i++) {
struct TreeNode *node = queue[i];
temp[i - begin] = node->val;
if(node->left != NULL) {
queue[size] = node->left;
size++;
}
if(node->right != NULL) {
queue[size] = node->right;
size++;
}
}
a[*returnSize] = temp;
(*returnSize)++;
begin = end;
end = size;
}
return a;
}