当前位置: 首页 > 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;无…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型

在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重&#xff0c;适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解&#xff0c;并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...

《Offer来了:Java面试核心知识点精讲》大纲

文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...

统计学(第8版)——统计抽样学习笔记(考试用)

一、统计抽样的核心内容与问题 研究内容 从总体中科学抽取样本的方法利用样本数据推断总体特征&#xff08;均值、比率、总量&#xff09;控制抽样误差与非抽样误差 解决的核心问题 在成本约束下&#xff0c;用少量样本准确推断总体特征量化估计结果的可靠性&#xff08;置…...

大模型真的像人一样“思考”和“理解”吗?​

Yann LeCun 新研究的核心探讨&#xff1a;大语言模型&#xff08;LLM&#xff09;的“理解”和“思考”方式与人类认知的根本差异。 核心问题&#xff1a;大模型真的像人一样“思考”和“理解”吗&#xff1f; 人类的思考方式&#xff1a; 你的大脑是个超级整理师。面对海量信…...

二叉树-144.二叉树的前序遍历-力扣(LeetCode)

一、题目解析 对于递归方法的前序遍历十分简单&#xff0c;但对于一位合格的程序猿而言&#xff0c;需要掌握将递归转化为非递归的能力&#xff0c;毕竟递归调用的时候会调用大量的栈帧&#xff0c;存在栈溢出风险。 二、算法原理 递归调用本质是系统建立栈帧&#xff0c;而非…...

【threejs】每天一个小案例讲解:创建基本的3D场景

代码仓 GitHub - TiffanyHoo/three_practices: Learning three.js together! 可自行clone&#xff0c;无需安装依赖&#xff0c;直接liver-server运行/直接打开chapter01中的html文件 运行效果图 知识要点 核心三要素 场景&#xff08;Scene&#xff09; 使用 THREE.Scene(…...