【Leetcode笔记】102.二叉树的层序遍历

目录

  • 知识点
  • Leetcode代码:
  • ACM模式代码:

知识点

  1. vector、queue容器的操作
  • vector<int> vec;做插入元素操作:vec.push_back(x)
  • queue<TreeNode*> que;做插入元素操作:que.push(root);。队列有四个常用的操作:push、pop、front、back,其中,push方法用于在队列的尾部插入一个元素,而pop方法用于移除队列的头部元素。front方法返回队列的第一个元素的引用,而back方法返回队列的最后一个元素的引用。
  1. 使用auto关键字来自动推断数据类型
for (const auto& level : result) {
    for (int val : level) {
        cout << val << " ";
    }
    cout << endl;
}

Leetcode代码:

/**
 * 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) 
    {
        queue<TreeNode*> que; // 辅助的队列
        vector<vector<int>> result; // 存放最后结果
        if(root)
        {
            que.push(root);
        }
        while(!que.empty())
        {
            int size = que.size(); // 每一层的节点个数,也是后面循环的次数
            vector<int> vec; // 存放每一层的节点值
            for(int i = 0; i < size; i++)
            {

                TreeNode* tmp = que.front();
                que.pop();
                vec.push_back(tmp->val);
                if(tmp->left)
                {
                    que.push(tmp->left);
                }
                if(tmp->right)
                {
                    que.push(tmp->right);
                }
            }

            result.push_back(vec);

        }
        return result;


    }
};

ACM模式代码:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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) {
        queue<TreeNode*> que; // 辅助的队列
        vector<vector<int>> result; // 存放最后结果
        if (root) {
            que.push(root);
        }
        while (!que.empty()) {
            int size = que.size(); // 每一层的节点个数,也是后面循环的次数
            vector<int> vec; // 存放每一层的节点值
            for (int i = 0; i < size; i++) {
                TreeNode* tmp = que.front();
                que.pop();
                vec.push_back(tmp->val);
                if (tmp->left) {
                    que.push(tmp->left);
                }
                if (tmp->right) {
                    que.push(tmp->right);
                }
            }
            result.push_back(vec);
        }
        return result;
    }
};

int main() {
    // 测试代码
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->left->left  = new TreeNode(7);
    root->left->right = new TreeNode(11);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    Solution solution;
    vector<vector<int>> result = solution.levelOrder(root);

    for (const auto& level : result) {
        for (int val : level) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}

测试用二叉树如下:
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515467.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Python系列】 yaml中写入数据

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

普联一面4.2面试记录

普联一面4.2面试记录 文章目录 普联一面4.2面试记录1.jdk和jre的区别2.java的容器有哪些3.list set map的区别4.get和post的区别5.哪个更安全6.java哪些集合类是线程安全的7.创建线程有哪几种方式8.线程的状态有哪几种9.线程的run和start的区别10.什么是java序列化11.redis的优…

深度解读DynamIQ架构cache的替换策略

快速链接: 【精选】ARMv8/ARMv9架构入门到精通-[目录] &#x1f448;&#x1f448;&#x1f448; 思考: 在经典的 DynamIQ架构 中&#xff0c;数据是什么时候存在L1 cache&#xff0c;什么时候存进L2 cache&#xff0c;什么时候又存进L3 cache&#xff0c;以及他们的替换策略是…

ArcGIS Pro导出布局时去除在线地图水印

目录 一、背景 二、解决方法 一、背景 在ArcGIS Pro中经常会用到软件自带的在线地图&#xff0c;但是在导出布局时&#xff0c;图片右下方会自带地图的水印 二、解决方法 解决方法&#xff1a;添加动态文本--服务图层制作者名单&#xff0c;然后在布局中选定位置添加 在状…

红蓝色WordPress外贸建站模板

红蓝色WordPress外贸建站模板 https://www.mymoban.com/wordpress/5.html

【Java】打包:JAR、EAR、WAR

打包&#xff1a;JAR、EAR、WAR war 是一个 Web 模块&#xff0c;其中需要包括 WEB-INF&#xff0c;是可以直接运行的 WEB 模块。而 jar 一般只是包括一些 class 文件&#xff0c;在声明了 main_class 之后是可以用 java 命令运行的。 它们都是压缩的包&#xff0c;拿 Tomcat …

LeetCode_234(回文链表)

//时间复杂度O(n) 空间复杂度O(1)public boolean isPalindrome(ListNode head) {ListNode fast head,slow head;while (fast !null && fast.next !null){fast fast.next.next;slow slow.next;}//如果链表是奇数个结点&#xff0c;把正中的归到左边if(fast ! null){s…

操作系统的信号量操作以及实战中的踩坑分析

往期地址&#xff1a; 操作系统系列一 —— 操作系统概述操作系统系列二 —— 进程操作系统系列三 —— 编译与链接关系操作系统系列四 —— 栈与函数调用关系操作系统系列五 —— 目标文件详解操作系统系列六 —— 详细解释【静态链接】操作系统系列七 —— 装载操作系统系列…

洛谷B3735题解

题目描述 圣诞树共有 n 层&#xff0c;从上向下数第 1 层有 1 个星星、第 2 层有 2 个星星、以此类推&#xff0c;排列成下图所示的形状。 星星和星星之间用绳子连接。第 1,2,⋯,n−1 层的每个星星都向下一层最近的两个星星连一段绳子&#xff0c;最后一层的相邻星星之间连一段…

【开发、测试】接口规范与测试

接口测试基础 url 是互联网标准资源地址&#xff0c;称为统一资源定位符 组成&#xff1a;协议&#xff0c;服务器地址&#xff0c;端口号 HTTP协议 HTTP&#xff1a;超文本传输协议&#xff0c;基于请求与响应的应用层协议 作用&#xff1a;规定了客户端和服务器之间的信…

Spring声明式事务以及事务传播行为

Spring声明式事务以及事务传播行为 Spring声明式事务1.编程式事务2.使用AOP改造编程式事务3.Spring声明式事务 事务传播行为 如果对数据库事务不太熟悉&#xff0c;可以阅读上一篇博客简单回顾一下&#xff1a;MySQL事务以及并发访问隔离级别 Spring声明式事务 事务一般添加到…

前端工程师————CSS学习

选择器分类 选择器分为基础选择器和复合选择器 基础选择器包括&#xff1a;标签选择器&#xff0c;类选择器&#xff0c;id选择器&#xff0c;通配符选择器标签选择器 类选择器 语法&#xff1a;.类名{属性1&#xff1a; 属性值&#xff1b;} 类名可以随便起 多类名使用方式&am…

LeetCode-98. 验证二叉搜索树【树 深度优先搜索 二叉搜索树 二叉树】

LeetCode-98. 验证二叉搜索树【树 深度优先搜索 二叉搜索树 二叉树】 题目描述&#xff1a;解题思路一&#xff1a;中序遍历解题思路二&#xff1a;0解题思路三&#xff1a;0 题目描述&#xff1a; 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树…

【蓝桥杯练习】tarjan算法求解LCA

还是一道比较明显的求LCA(最近公共祖先)模型的题目,我们可以使用多种方法来解决该问题&#xff0c;这里我们使用更好写的离线的tarjan算法来解决该问题。 除去tarjan算法必用的基础数组&#xff0c;我们还有一个数组d[],d[i]记录的是每个点的出度&#xff0c;也就是它的延迟时间…

氮气柜常用的制作材质有哪些?

氮气柜主要用于存储对湿度敏感或需要在低氧环境中保存的精密部件、电子元器件、化学品、文物等&#xff0c;需要确保柜体的密闭性和内部环境的稳定&#xff0c;以防止氧化、受潮或变质。 常见的材质有冷轧钢板&#xff0c;冷轧钢板通过冷轧工艺使钢材组织更紧密&#xff0c;从而…

LeetCode-543. 二叉树的直径【树 深度优先搜索 二叉树】

LeetCode-543. 二叉树的直径【树 深度优先搜索 二叉树】 题目描述&#xff1a;解题思路一&#xff1a;DFS解题思路二&#xff1a;另一种写法DFS解题思路三&#xff1a;0 题目描述&#xff1a; 给你一棵二叉树的根节点&#xff0c;返回该树的 直径 。 二叉树的 直径 是指树中任…

不能在主机和虚拟机之间拷贝文本(虚拟机ubuntu16.04)

问题 ubuntu16.04不能在主机和虚拟机之间拷贝文本。 原因 vmware tools没安装好。 解决办法 重新安装vmware tools&#xff0c;步骤入下&#xff1a; 让虚拟机加载C:\Program Files (x86)\VMware\VMware Workstation\linux.iso光盘文件&#xff0c;设置如下&#xff1a; …

C++的并发世界(四)——线程传参

1.全局函数作为传参入口 #include <iostream> #include <thread> #include <string>void ThreadMain(int p1,float p2,std::string str) {std::cout << "p1:" << p1 << std::endl;std::cout << "p2:" <<…

Linux安装conda

目录 conda是什么简介conda与miniconda、anaconda的关系 安装下载文件bash安装激活软件检查安装是否成功配置镜像源 创建环境 conda是什么 简介 conda是一个开源的包管理器和环境管理器&#xff0c;用于安装、运行和更新包和它们的依赖项。它可以轻松地在计算机上创建隔离的环…

刷题DAY44 | 完全背包问题 LeetCode 518-零钱兑换 II 377-组合总和 Ⅳ

完全背包问题模版 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品都有无限个&#xff08;也就是可以放入背包多次&#xff09;&#xff0c;求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题…