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

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...