当前位置: 首页 > news >正文

【代码随想录训练营】【Day15】第六章|二叉树|层序遍历|226.翻转二叉树|101.对称二叉树

层序遍历

题目详细:LeetCode.102

层序遍历与上一节讲的三种遍历方式有所不同,层序遍历是指按从上到下,从左到右的顺序,逐层地遍历二叉树的节点。

从其节点的遍历顺序上观察,我们可以发现其跟广度优先遍历(BFS)的遍历思想非常相似,既然我们可以利用队列先进先出的特点来实现广度优先遍历,那么我们也可以用队列来实现对二叉树的层序遍历:

  • 定义一个二维数组,其下标表示第i层,数组元素则存储着每一层遍历的节点
  • 定义一个队列,利用其先进先出的特点,先将非空的根节点进队
  • 定义一个循环,遍历入队的二叉树节点
    • 定义一个变量,记录每一层的节点数目,也就是当前队列的长度
    • 定义一个循环,获取变量得知在第一层,只有根节点一个节点
      • 那么我们只需要出队一次,将根节点出队,队列长度 - 1
      • 定义一个一维数组存放该层的节点值,并将该数组追加入到二维数组中
      • 然后将其非空的左右节点依次进队
      • 循环直到该层的节点都遍历完毕
  • 循环直到队列为空,说明二叉树层序遍历完成

Java解法(队列,BFS):

class Solution {public List<List<Integer>> ans = new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {this.bfs(root);return ans;}public void bfs(TreeNode root){Queue<TreeNode> queue = new LinkedList<>();if(null != root) queue.offer(root);while(!queue.isEmpty()){int n = queue.size();List<Integer> floor = new ArrayList<>();while(n-- > 0){TreeNode node = queue.poll();floor.add(node.val);if(null != node.left) queue.offer(node.left);if(null != node.right) queue.offer(node.right);}ans.add(floor);}}
}

这道题我们可以模拟层序遍历的思想,利用递归来解题,只需要在递归函数中增加一个变量,记录节点是第几层的即可:

Java解法(模拟,递归):

class Solution {public List<List<Integer>> ans = new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {this.order(root, 0);return ans;}public void order(TreeNode root, int level){if(null == root) return;if(level > ans.size() - 1){List<Integer> floor = new ArrayList<>();floor.add(root.val);ans.add(floor);}else{ans.get(level).add(root.val);}this.order(root.left, level + 1); this.order(root.right, level + 1); }
}

学会了二叉树的层序遍历后,可以一口气打完以下十道LeetCode题:

102.二叉树的层序遍历
104.二叉树的最大深度
107.二叉树的层次遍历II
111.二叉树的最小深度
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
199.二叉树的右视图
429.N叉树的层序遍历
515.在每个树行中找最大值
637.二叉树的层平均值


翻转二叉树

题目详细:LeetCode.226

翻转二叉树的过程和结果:
在这里插入图片描述
观察上图动画我们可以发现,上图采用的是层序遍历的顺序,在遍历的过程中,将每个节点的左右节点进行交换,这就是翻转二叉树的解题思想。

所以想要解题很简单,就是采用合适的遍历方法,在访问节点的时候,将其左右节点进行交换即可;

需要注意的是,在这道题中我们采用的遍历二叉树方法一般是:前序遍历、后序遍历和层序遍历,因为采用中序遍历的方式会导致重复交换子节点,需要在遍历过程中加以逻辑判断才能避免这一情况,不易编写和理解。

如何遍历在这里就不作赘述了,不了解的可以查看上一节的内容,详细讲述了遍历二叉树的各种方法:【Day14】传送门

Java解题(递归,前序遍历):

class Solution {public TreeNode invertTree(TreeNode root) {this.invertPre(root);return root;}public void swapChildNode(TreeNode node){TreeNode temp = node.left;node.left = node.right;node.right = temp;}public void invertPre(TreeNode root){if(null == root) return;this.swapChildNode(root);this.invertPre(root.left);this.invertPre(root.right);}
}

Java解题(统一迭代,前序遍历):

class Solution {public TreeNode invertTree(TreeNode root) {this.invertPre(root);return root;}public void swapChildNode(TreeNode node){TreeNode temp = node.left;node.left = node.right;node.right = temp;}public void invertPre(TreeNode root){Stack<TreeNode> stack = new Stack<>();if(null != root) stack.push(root);while(!stack.isEmpty()){// 标记节点TreeNode tagNode = stack.peek();if(tagNode != null){// 非标记节点,先弹出,在需要处理的节点后追加空指针作为标记(仅作标记,不作处理)TreeNode node = stack.pop();if(null != node.right) stack.push(node.right);if(null != node.left) stack.push(node.left);stack.push(node);stack.push(null);}else{// 遇到标记节点,先弹出作为标记的空指针的节点,再处理数据(处理节点,不作标记)stack.pop();TreeNode node = stack.pop();this.swapChildNode(node);}}}
}

对称二叉树

题目详细:LeetCode.101

由题可知,判断一棵二叉树是否对称:

  • 根节点无需比较
  • 接着比较树的内侧的节点和外侧的节点,而不是比较树的左右节点
  • 当每棵子树都满足内侧节点相等,外侧节点相等,那么则称这整棵二叉树是对称的

所以关键在于如何遍历二叉树,以及如何比较树的内侧节点和外侧节点。

既然根节点不需要比较,那么我们就需要同时比较其左右两棵子树上的节点,在比较过程中,会出现四种情况:

  • 左右节点皆为空,则是对称的
  • 左右节点只有一个为空,则是不对称的
  • 左右节点皆不为空,但是他们的值不相等,是不对称的
  • 左右节点皆不为空,但是他们的值相等,是对称的

所以对于每一棵子树,我们只需要按照上述情况去比较其内侧和外侧节点,就可以得到正确答案:

  • 树的内侧节点左子树的右节点和右子树的左节点进行比较
  • 树的外侧节点左子树的左节点和右子树的右节点进行比较
  • 当出现一种不对称情况时,则整个树是不对称的,无需继续比较
  • 当出现对称情况时,继续比较剩余的左右子树

Java解题(递归):

class Solution {public boolean isSymmetric(TreeNode root) {return this.check(root.left, root.right);}public boolean check(TreeNode leftNode, TreeNode rightNode){if(null == leftNode && null == rightNode) return true;else if(null == leftNode || null == rightNode || leftNode.val != rightNode.val) return false;return check(leftNode.right, rightNode.left) && check(leftNode.left, rightNode.right);}
}

Java解题(迭代,队列):

class Solution {public Queue<TreeNode> queue = new LinkedList<>();public boolean isSymmetric(TreeNode root) {return this.check(root.left, root.right);}public boolean check(TreeNode leftNode, TreeNode rightNode){this.queue.offer(leftNode);this.queue.offer(rightNode);while(!queue.isEmpty()){leftNode = queue.poll();rightNode = queue.poll();if(null == leftNode && null == rightNode)continue;else if(null == leftNode || null == rightNode || leftNode.val != rightNode.val){return false;        this.queue.offer(leftNode.right);this.queue.offer(rightNode.left);this.queue.offer(leftNode.left);this.queue.offer(rightNode.right);}return true;}
}

观察代码以及二叉树的遍历过程,我们也可以发现,对于对称二叉树的遍历顺序,左子树的遍历顺序是右左根,而右子树的遍历顺序是左右根,两者都属于后序遍历,也就是说,这道题是基于后序遍历来解决的。


除了在二叉树中常用的递归方法外,我们还可以结合前面学习的其他数据结构,如栈和队列,也能够辅助我们遍历和处理二叉树。

最后这两天做二叉树相关的题目之后,给我的感触就是,二叉树的题目千变万化,但是总结起来就是两个要点:选择最佳的遍历顺序 + 处理节点的需求逻辑,可见解答二叉树相关的题目时,理解和掌握二叉树不同的遍历思想是尤其重要的:

水之积也不厚,则其负大舟也无力。

相关文章:

【代码随想录训练营】【Day15】第六章|二叉树|层序遍历|226.翻转二叉树|101.对称二叉树

层序遍历 题目详细&#xff1a;LeetCode.102 层序遍历与上一节讲的三种遍历方式有所不同&#xff0c;层序遍历是指按从上到下&#xff0c;从左到右的顺序&#xff0c;逐层地遍历二叉树的节点。 从其节点的遍历顺序上观察&#xff0c;我们可以发现其跟广度优先遍历&#xff0…...

基于圆展开自适应三边测量算法的室内定位

基于圆展开自适应三边测量算法的室内定位 具有无线通信功能的移动设备的日益普及刺激了室内定位服务的增长。室内定位用于实时定位设备位置&#xff0c;方便访问。然而&#xff0c;由于大量障碍物&#xff0c;与室外定位相比&#xff0c;室内定位具有挑战性。全球定位系统非常适…...

使用中断子系统实现对LED灯的控制

中断顶半部&#xff1a;不允许耗时操作 代码流程&#xff1a; 1、基于字符设备驱动的注册&#xff08;手动/自动&#xff09; 2、基于设备树文件的自定义完成(myled, myirq) 2、基于GPIO子系统实现led的点亮&#xff08;流水/测试文件控制&#xff09; 3、中断子系统操作流程 …...

《爆肝整理》保姆级系列教程python接口自动化(十五)--参数关联接口(详解)

简介 我们用自动化新建任务之后&#xff0c;要想接着对这个新建任务操作&#xff0c;那就需要用参数关联了&#xff0c;新建任务之后会有一个任务的Jenkins-Crumb&#xff0c;获取到这个Jenkins-Crumb&#xff0c;就可以通过传这个任务Jenkins-Crumb继续操作这个新建的任务。 …...

【JDK8】MyBatis源码导入Idea

1.背景 为了更好的将MyBatis的开发设计思想带到日常开发工作&#xff0c;将MyBatis源码导入到本地开发工具中(idea)。我自己在导入的时候碰到几个问题&#xff0c;耽误了自己一点时间&#xff0c;这里我把它们记下来&#xff0c;后边的小伙伴可不要踩我的坑。 Java版本&#x…...

三层交换机DHCP中继

关于中继&#xff0c;我们需要有一个对比。正常情况下我们是不是需要配置单臂路由然后开启DHCP地址池&#xff0c;然就设置网段网关以及DNS。这样的话考验 的其实是命令功底。但是为了方便&#xff0c;我们 可以添加服务器&#xff0c;将这个服务给到服务器去配置&#xff0c;这…...

C++之RALL机制

RALL是Resource acquisition is initialization的缩写&#xff0c;意思是“资源获取即初始化”&#xff0c;其核心思想是利用C对象生命周期的概念来控制程序的资源。它的技术原理很简单&#xff0c;如果希望对某个重要资源进行跟踪&#xff0c;那么创建一个对象&#xff0c;并将…...

回溯算法章末总结

组合问题的特点 &#xff08;1&#xff09;abba 选中a之后&#xff0c;就不再选了 &#xff08;2&#xff09;找出所有的组合 &#xff08;长度可以不相等&#xff09; 组合问题模板 做回溯题步骤 &#xff08;0&#xff09;判断问题类型 &#xff08;1&#xff09;树状图 …...

【SpringBoot】为异步任务规划线程池

一、线程池的作用 防止资源占用无限的扩张调用过程省去资源的创建和销毁所占用的时间 在上一节中&#xff0c;我们的一个异步任务打开了一个线程&#xff0c;完成后销毁。在高并发环境下&#xff0c;不断的分配新资源&#xff0c;可能导致系统资源耗尽。所以为了避免这个问题…...

SAP ABAP 输出结果带有空格

方法一&#xff1a; 字段内容前增加空格&#xff0c;需使用全角空格&#xff0c;使用半角空格时&#xff0c;ALV显示无效&#xff0c;空格无法显示&#xff0c; 全角与半角的切换方法&#xff1a;shift空格切换&#xff0c; 如下的标记部分&#xff0c;要想通过ALV显示空格&…...

Opengl ES之踩坑记

前因 最近在尝试使用Opengl ES实现一些LUT滤镜效果&#xff0c;在实现这些滤镜效果的时候遇到一些兼容性的坑&#xff0c;踩过这些坑后我希望把这几个坑分享给读者朋友们&#xff0c; 希望同在学习Opengl ES的朋友们能少走弯路。 关于LUT滤镜相关的介绍&#xff0c;也是这个O…...

设计模式第六讲:责任链模式和迭代器模式详解

一. 责任链模式1. 背景在现实生活中&#xff0c;常常会出现这样的事例&#xff1a;一个请求有多个对象可以处理&#xff0c;但每个对象的处理条件或权限不同。例如&#xff0c;公司员工请假&#xff0c;可批假的领导有部门负责人、副总经理、总经理等&#xff0c;但每个领导能批…...

K8s 架构简介(一)

一、前言 在开始学习K8s之前&#xff0c;让我们对容器有一个基本的了解 1.1 什么是容器 一个容器镜像是一个可运行的软件包&#xff0c;其中包含了一个完整的可执行程序&#xff0c;包括代码和运行时需要应用、系统库和全部重要设置的默认值。 通过将应用程序本身&#xff…...

xshell6运行报错:由于找不到mfc110u.dll、MSVCR110.dll无法继续执行代码

今天给大家分享一下我刚装完系统遇到得问题,由于新盟的罗建雨【胡巴】老师帮我给电脑加了固态,又重装了系统,因此电脑里面得所有软件需要重装,在我重装的过程中遇到了一个小问题给大家分享一下,如果大家以后遇到也方便解决。 问题: 安装Xshell时电脑系统报错:“由于找…...

Baklib知识库管理平台,协助组织提升知识管理水平

随着信息时代和知识经济时代的到来&#xff0c;企业内部信息资料繁多冗杂&#xff0c;知识管理逐渐成为各大企业的重要工作之一&#xff0c;企业管理者无不感受到巨大的压力&#xff0c;怎么样将知识进行有效的管理&#xff0c;成为一个难点&#xff0c;并且随着信息不断的更迭…...

一文搞懂core-scheduling核心机制

cookie的原理借助于unsigned long型&#xff0c;和refcount_t引用计数器。 32位64位char *4字节8字节unsigned long4字节8字节 数据结构修改 首先看看实现core scheduling功能对数据结构有哪些修改 task_struct struct task_struct{struct rb_node core_node;unsigned long…...

IP地址在金融行业有哪些应用?

中国加入WTO以来经济得到迅速发展&#xff0c;金融行业随着经济发展体系越来越完善。随着西方金融公司和理念的加入中国金融行业开始多样化发展。金融行业在快速发展的同时也引发了许多弊端。如何维护挖掘客户更大需求&#xff1f;如何获取更多优质客户&#xff1f;如何提升网络…...

GT-suite v2016解决许可证过期问题(附新版liscense下载地址)

安装GT-suite v2016时遇到了如图报错的问题。当时的报错找不到了&#xff0c;下图是贴吧相同问题的报错图。 为了解决问题&#xff0c;先根据某网友的如下答复操作&#xff1a; 添加环境变量后仍然有相同报错。 看来需要寻找其他方法。 再尝试着卸载GT-suite v2016&#xff0c…...

小红书商业笔记与普通笔记区别是什么?小红书笔记有哪几种

主攻单一平台&#xff0c;如何迅速打造爆文。针对软文发布类别的选择&#xff0c;小红书商业笔记与普通笔记区别究竟是什么&#xff0c;今天为大家带来的详细分析&#xff0c;告诉你该如何用最少的成本&#xff0c;做出“爆文”。1、小红书的笔记类型我们都知道&#xff0c;小红…...

DataWhale-统计学习方法打卡Task01

学习教材《统计学习方法&#xff08;第二版&#xff09;》李航 统计学习方法&#xff08;第2版&#xff09; by...李航 (z-lib.org).pdf https://www.aliyundrive.com/s/maJZ6M9hrTe 点击链接保存&#xff0c;或者复制本段内容&#xff0c;打开「阿里云盘」APP &#xff0c;无…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...