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

【代码随想录训练营】【Day14】第六章|二叉树|理论基础|递归遍历|迭代遍历|统一迭代

理论基础

二叉树的定义形式有:节点指针和数组

  • 在数组中,父节点的下标为i,那么其左孩子的下标即i*2+1,右孩子的下标即为i*2+2

二叉树的常见遍历形式有:前序遍历、后序遍历、中序遍历和层序遍历

  • 前序遍历:二叉树的节点遍历顺序为,根节点、左节点、右节点,常记为“根左右”
  • 同理后序遍历则为“左右根”,中序遍历则为“左根右”,其主要的区别在于“根节点”的遍历顺序
  • 但是注意,访问顺序和遍历顺序不是相同的概念,例如中序遍历应该理解为已访问过中节点,只是未处理它,需要优先处理它的左节点
  • 层序遍历:顾名思义,就是按照从根节点到叶节点、从左到右的顺序,一层一层地遍历节点

根据二叉树的定义不同,又可分为不同类型的二叉树,常见的有:

  • 满二叉树:只有度为0的结点和度为2的节点,并且度为0的结点都在同一层上。
  • 完全二叉树:整颗树(包括其每一棵子树)除了叶节点,其他每一个节点都有左右节点(节点不为空),同时要保证父子节点的顺序关系
  • 二叉搜索树:整颗树(包括其每一棵子树)都满足左节点 < 父节点,右节点 > 父节点的条件,其中序遍历的结果为递增序列。
  • 二叉平衡树:整颗树(包括其每一棵子树)每一个节点都满足|其左右节点的树的高度的差值| <= 1

更多有关二叉树的理论基础可查阅:《代码随想录》二叉树理论基础

对于二叉树的遍历在《代码随想录》中都有非常详细的解释,我也是阅读学习之后再来解题的,所以在下面的解题过程中就不加以赘述了,仅贴出实现不同遍历形式的程序代码。


递归遍历二叉树

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

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();this.preorder(root, ans);return ans;}public void preorder(TreeNode root, List<Integer> list){if(null == root){return;}list.add(root.val);this.preorder(root.left, list);this.preorder(root.right, list);}
}

Java解法(递归,中序遍历):

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();this.inorder(root, ans);return ans;}public void inorder(TreeNode root, List<Integer> list){if(null == root){return;}this.inorder(root.left, list);list.add(root.val);this.inorder(root.right, list);}
}

Java解法(递归,后序遍历):

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();this.postorder(root, ans);return ans;}public void postorder(TreeNode root, List<Integer> list){if(null == root){return;}this.postorder(root.left, list);this.postorder(root.right, list);list.add(root.val);}
}

迭代遍历二叉树

Java解法(迭代,前序遍历):

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();this.preorder(root, ans);return ans;}public void preorder(TreeNode root, List<Integer> list){Stack<TreeNode> stack = new Stack<>();if(null != root) stack.push(root);while(!stack.isEmpty()){root = stack.pop();list.add(root.val);if(null != root.right) stack.push(root.right);if(null != root.left) stack.push(root.left);}}
}

Java解法(迭代,中序遍历):

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();this.inorder(root, ans);return ans;}public void inorder(TreeNode root, List<Integer> list){Stack<TreeNode> stack = new Stack<>();while(null != root || !stack.isEmpty()){if(null != root){stack.push(root);root = root.left;}else{root = stack.pop();list.add(root.val);root = root.right;}}}
}

Java解法(迭代,后序遍历):

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();this.postorder(root, ans);return ans;}public void postorder(TreeNode root, List<Integer> list){Stack<TreeNode> stack = new Stack<>();if(null != root) stack.push(root);while(!stack.isEmpty()){root = stack.pop();list.add(root.val);if(null != root.left) stack.push(root.left);if(null != root.right) stack.push(root.right);}Collections.reverse(list);}
}

我们发现迭代法实现的先中后序,其实风格也不是那么统一,除了先序和后序,有关联,中序完全就是另一个风格了,一会用栈遍历,一会又用指针来遍历。那么如何针对三种不同的遍历方式,使用迭代法是可以写出统一风格的代码?

统一迭代遍历二叉树【重点】

可以利用标记法来做到统一迭代:

  • 将访问的节点放入栈中,把要处理的节点也放入栈中但是要做标记。
  • 在这里,我们利用空指针来做标记,在要处理的节点放入栈之后,紧接着放入一个空指针作为标记。
  • 详细的解释和实现可以查阅:《代码随想录》二叉树的统一迭代法

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

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();this.preorder(root, ans);return ans;}public void preorder(TreeNode root, List<Integer> list){Stack<TreeNode> stack = new Stack<>();if(null != root) stack.push(root);while(!stack.isEmpty()){root = stack.peek();if(null != root){stack.pop(); // 需要先弹出节点,避免后续重复访问// 节点按照右左根的顺序进栈,后续出栈顺序为根左右(前序遍历)if(null != root.right) stack.push(root.right);if(null != root.left) stack.push(root.left);stack.push(root);stack.push(null); // 对需要处理的节点,在其后面跟上空指针作为标记}else{stack.pop(); // 遇到标记时,先弹出标记// 再弹出下一个节点进行处理root = stack.pop();list.add(root.val);}}}
}

Java解法(统一迭代,中序遍历):

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();this.inorder(root, ans);return ans;}public void inorder(TreeNode root, List<Integer> list){Stack<TreeNode> stack = new Stack<>();if(null != root) stack.push(root);while(!stack.isEmpty()){root = stack.peek();if(null != root){stack.pop(); // 需要先弹出节点,避免后续重复访问// 节点按照右根左的顺序进栈,后续出栈顺序为左根右(中序遍历)if(null != root.right) stack.push(root.right);stack.push(root);stack.push(null); // 对需要处理的节点,在其后面跟上空指针作为标记if(null != root.left) stack.push(root.left);}else{stack.pop(); // 遇到标记时,先弹出标记// 再弹出下一个节点进行处理root = stack.pop();list.add(root.val);}}}
}

Java解法(统一迭代,后序遍历):

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();this.postorder(root, ans);return ans;}public void postorder(TreeNode root, List<Integer> list){Stack<TreeNode> stack = new Stack<>();if(null != root) stack.push(root);while(!stack.isEmpty()){root = stack.peek();if(null != root){stack.pop();// 需要先弹出节点,避免后续重复访问// 节点按照根右左的顺序进栈,后续出栈顺序为左右根(后序遍历)stack.push(root);stack.push(null);// 对需要处理的节点,在其后面跟上空指针作为标记if(null != root.right) stack.push(root.right);if(null != root.left) stack.push(root.left);}else{stack.pop();// 遇到标记时,先弹出标记// 再弹出下一个节点进行处理root = stack.pop();list.add(root.val);}}}
}

二叉树结构也是在编程中常见的数据结构之一,例如堆其实就是一个树结构,以及哈希表中也运用到了红黑树来优化哈希表的存储结构等等。

通过今天的练习,我第一次了解并学习到了二叉树的统一迭代遍历算法,利用标记法来遍历二叉树的方法真的是非常巧妙,同时通过迭代算法的练习,也加深了对递归是如何模拟一个栈,以及递归算法如何转变为迭代算法有了一个初步的思路:

门径初窥书海奥, 欣喜若狂凯歌还。

相关文章:

【代码随想录训练营】【Day14】第六章|二叉树|理论基础|递归遍历|迭代遍历|统一迭代

理论基础 二叉树的定义形式有&#xff1a;节点指针和数组 在数组中&#xff0c;父节点的下标为i&#xff0c;那么其左孩子的下标即i*21&#xff0c;右孩子的下标即为i*22 二叉树的常见遍历形式有&#xff1a;前序遍历、后序遍历、中序遍历和层序遍历 前序遍历&#xff1a;二…...

AXI-Stream 学习笔记

参考 https://wuzhikai.blog.csdn.net/article/details/121326701 https://zhuanlan.zhihu.com/p/152283168 AXI4 介绍 AXI4 是ARM公司提出的一种片内总线&#xff0c;描述了主从设备之间的数据传输方式。主要有AXI4_LITE、AXI4_FULL、AXI4_STREAM三种。 AXI4_LITE&#xff1…...

【Linux】程序进程地址空间

文章目录程序地址空间进程地址空间程序地址空间 在Linux下,这种地址叫做 虚拟地址, 我们在用C/C语言所看到的地址,全部都是虚拟地址&#xff01;物理地址,用户一概看不到,由OS统一管理 问:C/C程序地址空间是内存吗? -> 根本就不是内存&#xff01; 是进程虚拟地址空间 堆栈…...

电压放大器在液滴微流控芯片的功能研究中的应用

实验名称&#xff1a;电压放大器在液滴微流控芯片的功能研究中的应用研究方向&#xff1a;微流控生物芯片测试目的&#xff1a;液滴微流控技术能够在微通道内实现液滴生成&#xff0c;精准控制生成液滴的尺寸以及生成频率。结合芯片结构设计和外部控制条件&#xff0c;可以对液…...

Linux操作系统学习(进程地址空间)

文章目录进程地址空间奇怪的现象什么是进程地址空间&#xff1f;&#xff1f;&#xff1f;虚拟地址是如何与物理内存联系的&#xff1f;页表是什么呢&#xff1f;为什么要有页表和地址空间&#xff0c;让进程直接访问内存不行吗&#xff1f;现象解释进程地址空间 在我们学习其…...

【排序】快速排序实现

目录 一、快速排序是什么&#xff1f; 二、左右指针法 1.实现原理 2.代码如下&#xff1a; 三、挖坑法 1.实现原理 2.代码如下&#xff1a; 四、前后指针法 1.实现原理 2.代码如下&#xff1a; 五、三数取中 1.实现思想 2.代码如下&#xff1a; 3.使用方法 总结…...

YOLOv5/v7 Flask Web 车牌识别 | YOLOv7 + EasyOCR 实现车牌识别

YOLOv7 Flask Web 车牌识别图片效果展示 本篇博文只包含源码以及使用方式,目前不同提供详细开发教程。 YOLOv7 Flask Web 车牌识别视频效果展示 YOLOv7 + EasyOCR 实现车牌识别 什么是Flask? 简介 Flask是一个轻量级的可定制框架,使用Python语言编写,较其他同类型框架更…...

【Opencv实战】几十年前的Vlog火了:黑白老照片如何上色?这黑科技操作一定要知道,复原度超高,竟美的出奇~(图像修复神级代码)

导语 哈喽大家好呀&#xff01;我是每天疯狂赶代码的木木子吖&#xff5e;情人节快乐呀&#xff01; 所有文章完整的素材源码都在&#x1f447;&#x1f447; 粉丝白嫖源码福利&#xff0c;请移步至CSDN社区或文末公众hao即可免费。 我们都知道&#xff0c;有很多经典的老照片…...

React源码分析(一)Fiber

前言 本次React源码参考版本为17.0.3。 React架构前世今生 查阅文档了解到&#xff0c; React16.x是个分水岭。 React15及之前 在16之前&#xff0c;React架构大致可以分为两层&#xff1a; Reconciler&#xff1a; 主要职责是对比查找更新前后的变化的组件&#xff1b;R…...

小樽 C++指针—— (壹) 指针变量

(壹) 指针变量 一、指针的概念与定义 二、给指针变量p赋值 三、指针变量的的、-运算 四、无类型指针 五、多重指针 C (壹) 指针变量 小明想把从李华家借来的书——《CCF中学生计算机程序设计》还给李华&#xff0c;但李华不在家&#xff0c;于是把书放到书架第3层的最右边…...

java 代码块 万字详解

概述 : 特点 : 格式 : 情景 : 细节 : 演示 : 英文 : //v&#xff0c;新版编辑器无手动添加目录的功能&#xff0c;PC端阅读建议通过侧边栏进行目录跳转&#xff1b;移动端建议用PC端阅读。&#x1f602;一、概述 :代码块&#xff0c;也称为初始化块&#xff0c;属于类中的成员&…...

杂项-图片隐写

图片隐写的常见隐写方法&#xff1a; 三基色&#xff1a;RGB&#xff08;Red Green Blue&#xff09; 图片文件隐写 1.Firework 使用winhex打开文件时会看到文件头部中包含firework的标识&#xff0c;通过firework可以找到隐藏图片。 使用场景&#xff1a;查看隐写的图片文件…...

【高性价比】初学者入门吉他值得推荐购买的民谣单板吉他品牌—VEAZEN费森吉他

“在未知的世界里&#xff0c;我们是一群不疲不倦的行者&#xff0c;执念于真善美&#xff0c;热衷于事物的极致。我们抽丝剥茧&#xff0c;不断地打败自己&#xff0c;超越自己&#xff0c;我们无所畏惧终将成为巨人。”这是VEAZEN吉他官网首页上很明显的一段话&#xff0c;也…...

2023年浙江交安安全员考试题库及答案

百分百题库提供交安安全员考试试题、交安安全员考试真题、交安安全员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 50.根据《建设工程安全生产管理条例》第65条规定&#xff0c;施工单位有下列&#xff08;&#xff09;行…...

【新】华为OD机试 - 跳格子(Python)

跳格子 题目 地上共有 N 个格子,你需要跳完地上所有的格子, 但是格子间是有强依赖关系的,跳完前一个格子后, 后续的格子才会被开启,格子间的依赖关系由多组 steps 数组给出, steps[0] 表示前一个格子, steps[1] 表示 steps[0] 可以开启的格子: 比如 [0,1] 表示从跳完第…...

乡村能做社区团购吗?怎么做?我走访调查后发现机会很大

乡村能做社区团购吗&#xff1f;怎么做&#xff1f;我走访调查后发现机会很大#深度触网 #社区团购 #乡村振兴##乡村旅游##县域经济##市场经济##农文旅产业振兴研究院#乡村旅游能带动农产品加工业、服务业、商贸业等相关联产业的发展 乡村能做社区团购吗&#xff1f;怎么做&…...

态路小课堂丨下一代数据中心100G接口第二篇——SFP-DD封装

100G光模块根据封装模式可分为QSFP28、CXP、CFP、CFP2、FCP4、DSFP和SFP-DD等。态路小课堂之前已经大量介绍了相关内容&#xff08;。 态路小课堂丨下一代数据中心100G接口——DSFP态路小课堂丨100G解决方案-425G NRZ光模块态路小课堂丨什么是100G QSFP28单波光模块&#xff1f…...

状态栏和导航栏高度获取

/*** 获取导航栏高度*/public static int getNavigationBarHeight(Context context){int navigationBarHeight 0;int resourceId context.getResources().getIdentifier("navigation_bar_height", "dimen", "android")if (resourceId > 0) {…...

插曲:第一桶金 1w 的来由

因为前天跟同事聊天&#xff0c;发现有个比较严重的认知&#xff0c;就是关于赚钱思维。 同事反馈说工作十来年&#xff0c;却没有接过私活&#xff0c;这里话分两头&#xff0c;有可能私 活钱少&#xff0c;但他给我的理由是&#xff1a;私活太麻烦&#xff0c;有时候不敢接&a…...

中国甲基异丁基甲醇行业头部企业市场占有率及排名调研报告

内容摘要 本文调研和分析全球甲基异丁基甲醇发展现状及未来趋势&#xff0c;核心内容如下&#xff1a; &#xff08;1&#xff09;全球市场总体规模&#xff0c;分别按销量和按收入进行了统计分析&#xff0c;历史数据2018-2022年&#xff0c;预测数据2023至2029年。 &#xf…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...