每日一题:LeetCode-103/107.二叉树的(层序/锯齿形层序)遍历

每日一题系列(day 04)

前言:

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

   🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,日日累积,终能成圣🙏🙏!开启我们今天的斩妖之旅吧!✈️✈️


  因为这两题具有很强的相似性,所以将两题放在一起。

一、LeetCode-107.二叉树的层序遍历 II

题目:

   给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

示例1:

在这里插入图片描述

示例2:

在这里插入图片描述

注意事项:

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

思路:

  本题和昨天写的题很像,只不过这次的层序遍历是要从叶子结点所在层向上进行层序遍历,既然我们使用二维数组来进行层序遍历,我们不妨先将正常的层序遍历保存到二维数组中,在正常的层序遍历完成之后,将二维数组的元素(一维数组,存的是每一层节点的值)首尾交换。

  我们再来回顾一下昨天说的二叉树层序遍历深搜的过程。
  1、深搜需要传入参数root, 从哪层开始处理的层数,二维数组ans,在dfs中,首先判断当前节点是否为空,如果为空就return;
  2、不过当前节点不为空,接下来就判断当前层数是否是最新遍历到的层数,如果是,在本层数组里压入元素之前需要创建一个空一维数组尾插到二维数组ans中。
   3、接下来就是将当前处理节点压入到对应层数的一维数组中,这个节点处理完毕,深搜就要开始递归处理,先向左子孩子处理,下一层为本层节点+1,所以传参层数为k + 1,同理右子树也是如此,最后返回即可。
 &emsp:4、深搜完成之后,我们就得到了一个自顶向下的层序遍历结果,我们想让结果自底向上遍历,只需ans的一维数组进行首尾交换,最后返回即可。
在这里插入图片描述

代码实现:

/*** 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:void dfs(TreeNode *root, int k, vector<vector<int>> &ans)//深搜方式进行层序遍历{if(root == NULL) return;if(k == ans.size()) ans.push_back(vector<int>());ans[k].push_back(root -> val);dfs(root -> left, k + 1, ans);dfs(root -> right, k + 1, ans);return;}vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> ans;dfs(root, 0, ans);//先将正常的层序遍历拿到for(int i = 0, j = ans.size() - 1; i < j ; i++, j--)//翻转正常的层序遍历,达到想要的效果{swap(ans[i], ans[j]);}return ans;//最后返回数组即可}
};

一、LeetCode-103.二叉树的锯齿形层序遍历

题目:

   给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

示例1:

在这里插入图片描述

示例2:

在这里插入图片描述

思路:

  这题要求我们层序遍历要螺旋遍历,第一层从左到右遍历这一层节点,第二层从右到左遍历这层节点,第三层还是从左到右…遍历呈现出一种螺旋型遍历。
  其实我们和上面107题一样,只需要先用深搜将正常的层序遍历结果拿到,在处理这个层序遍历的结果,拿到了正常层序遍历结果,我们来观察:
在这里插入图片描述
  我们可以发现,我们遍历时需要翻转的总是偶数层,所以我们翻转的时候只需要处理偶数层的一维数组就可以了。

代码实现:

/*** 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:void dfs(TreeNode *root, int k, vector<vector<int>> &ans){if(root == NULL) return;if(k == ans.size()) ans.push_back(vector<int>());ans[k].push_back(root -> val);dfs(root -> left, k + 1, ans);dfs(root -> right, k + 1, ans);return;}vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ans;dfs(root, 0, ans);//深搜for(int k = 1 ; k < ans.size() ; k += 2)//偶数层才翻转{for(int i = 0, j = ans[k].size() - 1 ; i < j ; i++, j--)//将需要翻转的层进行翻转{swap(ans[k][i], ans[k][j]);}}return ans;//返回翻转后的数组即可}
};

  这两题的相似度很高,我这里都是使用深搜的方式得到正常层序遍历的结果,当然你可以使用队列的形式得到层序遍历结果,这里就不展示了,这两题的不用是对层序遍历的结果的处理,转换成另外的形式。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

成为AI产品经理——模型构建过程(上)

目录 一、背景 1.对内 2.对外 二、模型构建过程 1.模型设计 2.特征工程 ① 数据清洗 ② 特征提取 数值型数据 标签/描述类数据特征 非结构化数据&#xff08;处理文本特征&#xff09; 网络关系型数据 ③ 特征选择 ④ 训练集/测试集 一、背景 虽然产品经理不…

基于SSM的网络财务管理系统设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用JSP技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…

nuxt、vue实现PDF和视频文件的上传、下载、预览

上传 上传页面 <el-form-item :label"(form.ququ3 1 ? 参培 : form.ququ3 2 ? 授课 : ) 证明材料" prop"ququ6"><PdfUpload v-model"form.ququ6" :fileType"[pdf, mp4, avi, ts]"></PdfUpload> </el-form-i…

Java游戏制作——王者荣耀

一.准备工作 首先创建一个新的Java项目命名为“王者荣耀”&#xff0c;并在src下创建两个包分别命名为“com.sxt"、”com.stx.beast",在相应的包中创建所需的类。 创建一个名为“img”的文件夹来储存所需的图片素材。 二.代码呈现 package com.sxt;import javax.sw…

Android开源框架--Dagger2详解

功名只向马上取&#xff0c;真是英雄一丈夫 一&#xff0c;定义 我们知道在一个类中&#xff0c;通常会定义其他类型的变量&#xff0c;这个变量就是我们所说的“依赖“。 对一个类的变量进行初始化&#xff0c;有两种方式。第一种&#xff0c;这个类自己进行初始化&#xff…

【Vue】Vue3 配置全局 scss 变量

variables.scss $color: #0c8ce9;vite.config.ts // 全局css变量css: {preprocessorOptions: {scss: {additionalData: import "/styles/variables.scss";,},},},.vue 文件使用

血的教训------入侵redis之利用python来破解redis密码

血的教训------入侵redis之利用python来破解redis密码 利用强大的python来进行redis的密码破解&#xff0c;过程不亦乐乎&#xff0c;当然也可以用shell脚本 本篇文章只供学习交流&#xff0c;请勿他用&#xff0c;谢谢。 其他相关联的文章 [1]VMware安装部署kail镜像服务器【…

Spring Boot创建和使用(重要)

Spring的诞生是为了简化Java程序开发的&#xff01; Spring Boot的诞生是为了简化Spring程序开发的&#xff01; Spring Boot就是Spring框架的脚手架&#xff0c;为了快速开发Spring框架而诞生的&#xff01;&#xff01; Spring Boot的优点&#xff1a; 快速集成框架&#x…

git的用法

目录 一、为什么需要git 二、git基本操作 2.1、初始化git仓库 2.2、配置本地仓库的name和email 2.3、认识工作区、暂存区、版本库 三、git的实际操作 3.1 提交文件 3.2 查看git状态以及具体的修改 3.3 git版本回退 git reset 3.1 撤销修改 四、git分支管理 4.…

fastjson和jackson序列化的使用案例

简单记录一下一个fastjson框架和jackson进行序列化的使用案例&#xff1a; 原json字符串&#xff1a; “{“lockCount”:”{1:790,113:1,2:0,211:0,101:1328,118:8,137:0,301:0,302:0}“,“inventoryCount”:”{1:25062,113:2,2:10000,211:2,101:11034,118:9,137:40,301:903914…

【数据库】聊聊一颗B+树 可以存储多少数据

我们知道数据库使用的数据结构是B树&#xff0c;但是B树可以存储多少数据呢&#xff0c;在面试中也是经常会问的问题&#xff0c;所以我们从根上理解这个问题。 操作系统层面 数据都是存储在磁盘中的&#xff0c;而磁盘中的数据都是以最新单位扇区进行分割。一个扇区的大小是…

大数据平台/大数据技术与原理-实验报告--MapReduce编程

实验名称 MapReduce编程 实验性质 &#xff08;必修、选修&#xff09; 必修 实验类型&#xff08;验证、设计、创新、综合&#xff09; 综合 实验课时 2 实验日期 2023.10.30-2023.11.03 实验仪器设备以及实验软硬件要求 专业实验室&#xff08;配有centos7.5系统…

Cortex-M与RISC-V区别

环境 Cortex-M以STM32H750为代表&#xff0c;RISC-V以芯来为代表 RTOS版本为RT-Thread 4.1.1 寄存器 RISC-V 常用汇编 RISC-V 关于STORE x4, 4(sp)这种寄存器前面带数字的写法&#xff0c;其意思为将x4的值存入sp4这个地址&#xff0c;即前面的数字表示偏移的意思 反之LOA…

论文阅读:“Model-based teeth reconstruction”

文章目录 AbstractIntroductionTeeth Prior ModelData PreparationParametric Teeth Model Teeth FittingTeeth Boundary Extraction Reference Abstract 近年来&#xff0c;基于图像的人脸重建方法日趋成熟。这些方法可以捕捉整个面部或面部特定区域&#xff08;如头发、眼睛…

探索H5的神秘世界:测试点解析

Html5 app实际上是Web app的一种&#xff0c;在测试过程中可以延续Web App测试的部分方法&#xff0c;同时兼顾手机端的一些特性即可&#xff0c;下面帮大家总结下Html5 app 相关测试方法&#xff01; app内部H5测试点总结 1、业务逻辑 除基本功能测试外&#xff0c;需要关注的…

【微服务专题】微服务架构演进

目录 前言阅读对象阅读导航前置知识笔记正文一、系统架构的演变1.1 单体架构1.2 单体水平架构1.3 垂直架构1.4 SOA架构1.5 微服务架构 二、如何实现微服务架构2.1 微服务架构下的技术挑战2.2 微服务技术栈选型2.3 什么是Spring Cloud全家桶2.4 Spring Cloud Alibaba版本选择 学…

智慧化工~工厂设备检修和保全信息化智能化机制流程

化工厂每年需要现场检修很多机器&#xff0c;比如泵、压缩机、管道、塔等等&#xff0c;现场检查人员都是使用照相机&#xff0c;现场拍完很多机器后&#xff0c;回办公室整理乱糟糟的照片&#xff0c;但是经常照了之后无法分辨是哪台设备&#xff0c;而且现场经常漏拍&#xf…

HarmonyOS4.0系列——02、汉化插件、声明式开发范式ArkTS和类web开发范式

编辑器调整 我们在每次退出编辑器后再次打开会直接进入项目文件中&#xff0c;这样在新建项目用起来很是不方便&#xff0c;所以这里跟着设置一下就好 这样下次进入就不会直接跳转到当时的文件项目中&#xff01;&#xff01; 关于汉化 settings → plugins → installe…

耗时一个星期整理的APP自动化测试工具大全

在本篇文章中&#xff0c;将给大家推荐14款日常工作中经常用到的测试开发工具神器&#xff0c;涵盖了自动化测试、APP性能测试、稳定性测试、抓包工具等。 一、UI自动化测试工具 1. uiautomator2 openatx开源的ui自动化工具&#xff0c;支持Android和iOS。主要面向的编程语言…

西南科技大学数字电子技术实验二(SSI逻辑器件设计组合逻辑电路及FPGA实现 )预习报告

一、计算/设计过程 说明:本实验是验证性实验,计算预测验证结果。是设计性实验一定要从系统指标计算出元件参数过程,越详细越好。用公式输入法完成相关公式内容,不得贴手写图片。(注意:从抽象公式直接得出结果,不得分,页数可根据内容调整) 1、1位半加器 真值表: 逻…