LeetCode102. 二叉树的层序遍历(2024秋季每日一题 43)

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

示例 1:
在这里插入图片描述

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

提示:

树中节点数目在范围 [ 0 , 2000 ] [0, 2000] [0,2000]
− 1000 < = N o d e . v a l < = 1000 -1000 <= Node.val <= 1000 1000<=Node.val<=1000


解法一:
思路:

  • 每层一个 vector,相当于二维数组的一行
  • 每次遍历一行(一层)
  • 对于每层遍历:
    • 新创建一个 vector,用于记录下一层的节点
    • 如果当前节点做左子节点,则加入 下层的 vector 数组
    • 如果当前节点做右子节点,则加入 下层的 vector 数组
  • 逐层遍历,直到没有下一层
/**
 * 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) {
        vector<vector<TreeNode*>> res;
        vector<vector<int>> ans;
        if(root == nullptr) return ans;
        int l = 0;
        while(res.size() >= l){
            vector<TreeNode*> v;
            vector<int> q;
            if(!l) v.push_back(root), q.push_back(root -> val);
            else{
                int n = res[l-1].size();
                for(int i = 0; i < n; i++){
                    TreeNode* cur = res[l-1][i];
                    if(cur -> left != nullptr) v.push_back(cur -> left), q.push_back(cur -> left -> val);
                    if(cur -> right != nullptr) v.push_back(cur -> right), q.push_back(cur -> right -> val);
                }
            }
            if(v.size()) res.push_back(v);
            if(q.size()) ans.push_back(q);
            l++;
        }
        return ans;
    }
};

解法二:
思路:

  • 通过队列来进行搜索(bfs)
  • 在 bfs 基础上,遍历每层前,用 temp 变量 提前记录 当前层最后一个节点的位置
  • 遍历当前层的每个节点
    • 如果当前节点做左子节点,则加入 下层的 vector 数组
    • 如果当前节点做右子节点,则加入 下层的 vector 数组
  • 逐层遍历,直到没有下一层
/**
 * 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) {
        vector<vector<int>> ans;
        TreeNode* q[2010];
        if(root == nullptr) return ans;
        int hh = 0, tt = -1;
        q[++tt] = root;
        vector<int> v;
        v.push_back(root -> val);
        ans.push_back(v);
        while(hh <= tt){
            int temp = tt;
            vector<int> v;
            while(hh <= temp){
                auto cur = q[hh++];
                if(cur -> left != nullptr) q[++tt] = cur -> left, v.push_back(q[tt]->val);
                if(cur -> right != nullptr) q[++tt] = cur -> right, v.push_back(q[tt]->val);
            }
            if(v.size()) ans.push_back(v);
        }
        return ans;
    }
};

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

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

相关文章

React 项目热更新失效问题的解决方案和产生的原因

背景和意义 在修复React项目热更新失效的问题时&#xff0c;经过一系列问题排查和依赖升级&#xff0c;最终成功修复了问题并为后续开发规避了类似的问题。 依赖升级 Vite版本升级 原React项目Vite版本升级到^4.4.5 Vite 4 在构建和开发服务器的性能上进行了优化&#xff…

气膜高尔夫:不惧天气,挥杆无忧—轻空间

高尔夫是一项户外运动&#xff0c;但恶劣天气常常成为阻碍。然而&#xff0c;在气膜高尔夫球馆中&#xff0c;无论外面下雨或酷暑&#xff0c;内部环境始终保持宜人&#xff0c;提供理想的打球体验。气膜技术为球员打造了一个全天候的运动空间&#xff0c;彻底摆脱了天气的束缚…

【中危】Oracle TNS Listener SID 可以被猜测

一、漏洞详情 Oracle 打补丁后&#xff0c;复测出一处中危漏洞&#xff1a;Oracle TNS Listener SID 可以被猜测。 可以通过暴力猜测的方法探测出Oracle TNS Listener SID&#xff0c;探测出的SID可以用于进一步探测Oracle 数据库的口令。 建议解决办法&#xff1a; 1. 不应该使…

大数据治理:数据时代的挑战与应对

目录 大数据治理&#xff1a;数据时代的挑战与应对 一、大数据治理的概念与内涵 二、大数据治理的重要性 1. 提高数据质量与可用性 2. 确保数据安全与合规 3. 支持数据驱动的决策 4. 提高业务效率与竞争力 三、大数据治理的实施策略 1. 建立健全的数据治理框架 2. 数…

【Linux系统编程】冯诺依曼体系结构与操作系统

目录 1、冯诺依曼体系结构 1.1 冯诺依曼体系结构的组成 1.2 程序运行时必须要加载到内存 1.3 数据通信 1.4 为什么要有内存 2、操作系统 2.1 概念 2.2 设计OS的目的 2.3 如何理解管理 2.4 系统调用和库函数的概念 1、冯诺依曼体系结构 我们常见的计算机&#xff0c;如…

5g工业路由器最新案例:高原气象站网络升级项目

背景&#xff1a; 某省气象局决定在高原地区升级其气象观测网络&#xff0c;以提高天气预报的准确性和及时性&#xff0c;同时为气候变化研究提供更可靠的数据支持。该项目面临以下挑战&#xff1a; 需要在高原广袤且地形复杂的区域部署大量自动气象站&#xff0c;要求网络覆…

JAVA八股

快速失败&#xff08;fail-fast&#xff09; 设计的目的是为了避免在遍历时对集合进行并发修改&#xff0c;从而引发潜在的不可预料的错误。 通过迭代器遍历集合时修改集合&#xff1a; 如果你使用Iterator遍历集合&#xff0c;然后直接使用集合的修改方法&#xff08;如add(…

C++20中头文件span的使用

<span>是C20中新增加的头文件&#xff0c;此头文件是containers库的一部分。包括&#xff1a; 1.模板类std::span&#xff1a;连续对象序列的非拥有视图(view)。std::span可以具有static extent&#xff0c;在这种情况下&#xff0c;序列中的元素数量在编译时已知并以typ…

FPGA实现PCIE采集电脑端视频转SFP光口UDP输出,基于XDMA+GTX架构,提供4套工程源码和技术支持

目录 1、前言工程概述免责声明 2、相关方案推荐我已有的PCIE方案1G/2.5G Ethernet Subsystem实现物理层方案1G/2.5G Ethernet PCS/PMA or SGMII Tri Mode Ethernet MAC实现物理层方案 3、PCIE基础知识扫描4、工程详细设计方案工程设计原理框图电脑端视频PCIE视频采集QT上位机X…

视频转文字工具搜集

视频转文字工具是一种能够将视频中的音频内容转化为文字的软件或在线服务。这类工具通常支持多种视频格式和语言&#xff0c;适用于不同的场景和需求。以下是一些推荐的视频转文字工具及其特点&#xff1a; 媒关系&#xff1a;这是一款免费的视频转文字工具&#xff0c;支持多种…

THP4 SOP16 芯片 高速光耦芯片

光电耦合器输入端加电信号使发光源发光&#xff0c;光的强度取决于激励电流的大小&#xff0c;此光照射到封装在一起的受光器上后&#xff0c;因光电效应而产生了光电流&#xff0c;由受光器输出端引出&#xff0c;这样就实现了电一光一电的转换。 由于光耦合器输入输出间互相…

k8s ETCD数据备份与恢复

在 Kubernetes 集群中&#xff0c;etcd 是一个分布式键值存储&#xff0c;它保存着整个集群的状态&#xff0c;包括节点、Pod、ConfigMap、Secrets 等关键信息。因此&#xff0c;定期对 etcd 进行备份是非常重要的&#xff0c;特别是在集群发生故障或需要恢复数据的情况下。本文…

完美搭建web自动化环境

在快速发展的科技时代&#xff0c;自动化测试已成为提高软件质量和开发效率的关键。今天&#xff0c;我们将揭示如何使用Java语言完美搭建Web自动化环境&#xff0c;为你的测试之旅打下坚实的基础&#xff01; 你是否在为搭建一个稳定高效的Web自动化测试环境而感到困惑&#…

DS快速排序和归并排序的非递归实现(16)

文章目录 前言一、快排的非递归实现二、归排的非递归实现总结 前言 打破递归桎梏&#xff0c;迎接迭代解放&#xff01; 一、快排的非递归实现 我们要替代递归&#xff0c;就要用到迭代或者循环&#xff0c;也就是说&#xff0c;其核心思想是不变的&#xff0c;只是换一种方式来…

VMware:Windows主机与CentOS虚拟机文件互传文件共享

注意&#xff1a;本文使用Win10与VMware17pro互传 1. 本地创建文件夹 如下图创建一个文件夹&#xff0c;名字任意 2. 设置本地文件夹权限 右键文件夹 - - 属性 - - 共享 - - 高级共享 - - 权限 - - 如下图全部勾选 - - 应用 - - 确认 3. VMware中设置共享文件夹路径 第一步…

宿主机无法通过WinSCP连接虚拟机

排查步骤 1. 检查虚拟机是否启用了 SSH 服务 WinSCP 连接虚拟机需要 SSH 服务在虚拟机中运行。 检查 SSH 服务状态&#xff1a; 在虚拟机中执行以下命令&#xff1a;sudo systemctl status ssh 如果 SSH 服务未启动&#xff1a; sudo systemctl start ssh sudo systemct…

测试睡眠质量的app免费

测试睡眠质量的app免费&#xff0c;在快节奏的现代社会中&#xff0c;优质的睡眠对我们的身体健康和精神状态都至关重要。然而&#xff0c;许多人却面临睡眠质量不佳的问题。为了帮助大家更好地了解自己的睡眠状况&#xff0c;我们将介绍十款免费的睡眠质量测试APP&#xff0c;…

C#学习笔记(十一)

C#学习笔记&#xff08;十一&#xff09; 第八章 垃圾回收机制GC与类的静态方法一、垃圾回收机制GC1. 对象如何被销毁的 二、类的静态方法1. 静态方法的使用2. 为什么会报错2.1 静态方法定义中的报错2.2 方法使用中的报错 3. 什么情况下用静态 第八章 垃圾回收机制GC与类的静态…

CSS 居中那些事

一、父子元素高度确定 简单粗暴, 直接通过设置合适的 padding 或 margin 实现居中 <style>.p {padding: 20px 0;background: rgba(255, 0, 0, 0.1);}.c {width: 40px;height: 20px;background: blue;} </style> <div class"p"><div class"…

第 5 章:vuex

1. 理解 vuex vuex 是什么&#xff1a; 概念&#xff1a;专门在 Vue 中实现集中式状态&#xff08;数据&#xff09;管理的一个 Vue 插件&#xff0c;对 vue 应用中多个组件的共享状态进行集中式的管理&#xff08;读/写&#xff09;&#xff0c;也是一种组件间通信的方式&am…