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

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

rknn toolkit2搭建和推理

安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 &#xff0c;不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源&#xff08;最常用&#xff09; conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...