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

代码随想录算法训练营第十四天(py)| 二叉树 | 递归遍历、迭代遍历、统一迭代

1 理论基础

1.1 二叉树的种类

满二叉树

只有度为0和2的节点,且度为0的节点在同一层。
深度为k,有2^k-1个节点
满二叉树

完全二叉树

除了最底层可能没填满,其余每层节点数都达到最大。并且最底层节点全部集中在左边。
在这里插入图片描述

二叉搜索树

是一个有数值的有序树。左子树的所有节点均小于根节点,右子树的所有节点均大于根节点。
在这里插入图片描述
大的放右边,小的放左边。

平衡二叉搜索树。

若非空,则左右两个子树的高度差不超过1,并且两个子树都是平衡二叉树
在这里插入图片描述

1.2 二叉树的存储

链式存储

用指针。一般用这个
在这里插入图片描述

顺序存储

用数组
在这里插入图片描述
若父节点的数组下标为i,则左子节点下标为2i+1,右子节点下标为2i+2。

1.3 二叉树的遍历方式

深度优先遍历:往深里走,直到碰到叶子节点。
-前序遍历:中左右
-中序遍历:左中右
-后序遍历:左右中
广度优先遍历:一层一层走
在这里插入图片描述
python下的树定义:

class TreeNode:def __init__(self, val, left=None, right=None):self.val = val # 值self.left = left # 左指针self.right = right # 右指针

2 递归遍历

每次写递归要按照以下三要素来写:

  1. 确定递归函数的参数和返回值。
  2. 确定终止条件
  3. 确定单层递归的逻辑

2.1 前序递归(中左右)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:res = []def dfs(node):if node is None:returnres.append(node.val)dfs(node.left)dfs(node.right)dfs(root)return res

2.1 中序递归(左中右)

class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:res = []def dfs(node):if node is None:returndfs(node.left)res.append(node.val)dfs(node.right)dfs(root)return res

2.3 后序递归(左右中)

class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:res = []def dfs(node):if node is None:returndfs(node.left)dfs(node.right)res.append(node.val)dfs(root)return res

3 迭代遍历

需要创建一个数组res用于保存结果,和一个栈stack用于保存当前节点。迭代中有两个操作:

  1. 处理当前节点:将元素放入res中
  2. 遍历节点

3.1 前序迭代遍历(中左右)

先将根节点压栈,然后右子节点压栈,然后左子节点压栈
注意:这里和中左右的顺序是相反的!因为这么做出栈的时候才是正确的顺序

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:stack = [root]res = []if root == None:return reswhile stack: # 当栈非空时node = stack.pop()res.append(node.val) # 中结点先处理if node.right: # 右孩子先入栈stack.append(node.right)if node.left:  # 左孩子后入栈stack.append(node.left)return res

3.2 中序迭代遍历(左中右)

中序迭代遍历的代码不与前序的通用,因为处理顺序和访问顺序不一样。

class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:res = []stack = [] # 不能提前将root放入stackcur = root # 当前节点if root == None:return reswhile cur or stack: # 当当前节点和栈有一个非空时if cur != None:stack.append(cur)cur = cur.left  # 先一直靠左深入else: # 当左边走到头了,处理栈顶节点cur = stack.pop()res.append(cur.val) # 中cur = cur.right # 右return res

3.3 后序迭代遍历(左右中)

调整前序遍历的顺序即可,将res反转。
注意,反转前res的顺序为中右左,因此入栈的顺序应该左孩子先入栈,右孩子后入栈。

class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:res = []stack = [root]if root == None:return reswhile stack:node = stack.pop()res.append(node.val)if node.left:stack.append(node.left)# 左孩子先入栈if node.right:stack.append(node.right)# 右孩子后入栈return res[::-1] #反转

4 统一迭代

其实针对三种遍历方式,使用迭代法是可以写出统一风格的代码。
就将访问的节点放入栈中,把要处理的节点也放入栈中但是要做标记。要处理的节点放入栈之后,紧接着放入一个空指针作为标记。

4.1 前序遍历(中左右)

class Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:res = []stack = [root]if root == None:return reswhile stack:if node != None:if node.right:stack.append(node.right)if node.left:stack.append(node.left)stack.append(node) # 把访问的节点和要处理的节点都入栈stack.append(None) # 并且在要处理的节点之后添加一个空值else:node = stack.pop()res.append(node.val)return res

4.2 中序遍历(左中右)

class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:res = []stack = [root]if root == None:return reswhile stack:node = stack.pop()if node != None:if node.right:stack.append(node.right)stack.append(node)stack.append(None)if node.left:stack.append(node.left)else:node = stack.pop()res.append(node.val)return res

4.3 后序遍历(左右中)

class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:res = []stack = [root]if root == None:return reswhile stack:node = stack.pop()if node != None:stack.append(node)stack.append(None)if node.right != None:stack.append(node.right)if node.left != None:stack.append(node.left)else:node = stack.pop()res.append(node.val)return res

相关文章:

代码随想录算法训练营第十四天(py)| 二叉树 | 递归遍历、迭代遍历、统一迭代

1 理论基础 1.1 二叉树的种类 满二叉树 只有度为0和2的节点,且度为0的节点在同一层。 深度为k,有2^k-1个节点 完全二叉树 除了最底层可能没填满,其余每层节点数都达到最大。并且最底层节点全部集中在左边。 二叉搜索树 是一个有数值…...

Golang并发编程-协程goroutine初体验

文章目录 前言一、Goroutine适合的使用场景二、Goroutine的使用1. 协程初体验 三、WaitGroupWaitGroup 案例一WaitGroup 案例二 总结 前言 学习Golang一段时间了,一直没有使用过goroutine来提高程序执行效率,在一些特殊场景下,还是有必须开启…...

驱动与系统学习网址

DRM(Direct Rendering Manager)学习简介-CSDN博客 Android Qcom Display学习(零)-CSDN博客 https://blog.csdn.net/hexiaolong2009/category_9705063.htmlhttps://blog.csdn.net/hexiaolong2009/category_9705063.htmlRender Hell —— 史上最通俗易懂…...

OAuth2.0

OAuth2.0 OAuth2.0是一种授权框架,用于授权第三方应用访问用户资源的方式。它允许用户将自己的信息(如照片、视频等)存储在一个服务提供商中,然后授权第三方应用访问这些信息,而无需提供用户名和密码给第三方应用。OAu…...

测试testing10

测试testing10...

在Java中实现泛型(Generics)的深入解析

在Java中,泛型(Generics)是一个强大的工具,它允许我们在编译时定义类型参数,使代码更加灵活、可重用和类型安全。下面,我将从技术难点、面试官关注点、回答吸引力以及代码举例四个方面,详细解析…...

每周题解:繁忙的都市

题目链接 繁忙的都市 题目描述 城市 C 是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市 C 的道路是这样分布的:城市中有 n n n 个交叉路口,有些交叉路口之间有道路相连,两…...

linux之防火墙工具

netfilter Linux防火墙是由Netfilter组件提供的,Netfilter工作在内核空间,集成在linux内核中。 Netfilter在内核中选取五个位置放了五个hook(勾子) function(INPUT、OUTPUT、FORWARD、PREROUTING、POSTROUTING),而这五个hook function向用户…...

【Python】—— 高阶函数

目录 (一)体验高阶函数 (二)内置高阶函数 2.1 map() 2.2 reduce() 2.3 filter() Python中的高阶函数是指那些接受函数作为参数,或者返回函数作为结果的函数。这种特性让Python的函数编程能力非常强大&…...

逻辑分析仪 - 采样率/采样深度

采样深度(Sampling Depth) 采样深度指的是逻辑分析仪在一次捕获过程中可以记录的最大样本数量。简单来说,采样深度越大,逻辑分析仪可以记录的数据量就越多。这对于分析长时间的信号变化或复杂的信号序列非常重要。 采样率&#…...

【Maven打包将resources/lib/下的jar也打包进jar包中】

Maven打包将resources/lib/下的jar也打包进jar包中 &#xff01;&#xff01;&#xff01;少走弯路 第一步 resources/lib/下引入jar ftp4j-1.7.2.jar替换为自己jar包的名称 <dependency><groupId>it.sauronsoftware.ftp4j</groupId><artifactId>ft…...

基于Java的地震震中附近城市分析实战

目录 前言 一、空间数据说明 1、空间查询 二、Java后台开发 1、模型层设计与实现 2、控制层设计与实现 三、Leaflet地图开发 1、地震震中位置展示 2、附近城市展示 3、成果展示 总结 前言 随着全球气候变化和地壳活动的不断演变&#xff0c;地震作为一种自然灾害&…...

【C语言】指针(三)

目录 一、字符指针 1.1 ❥ 使用场景 1.2 ❥ 有关字符串笔试题 二、数组指针 2.1 ❥ 数组指针变量 2.2 ❥ 数组指针类型 2.3 ❥ 数组指针的初始化 三、数组指针的使用 3.1 ❥ 二维数组和数组名的理解 3.2 ❥ 二维数组传参 四、函数指针 4.1 ❥ 函数的地址 4.2 ❥ 函数…...

【Linux】从零开始认识进程间通信 —— 管道

送给大家一句话&#xff1a; 人要成长&#xff0c;必有原因&#xff0c;背后的努力与积累一定数倍于普通人。所以&#xff0c;关键还在于自己。 – 杨绛 从零开始认识进程间通信 1 为什么要进程间通信2 进程如何通信3 进程通信的常见方式4 管道4.1 什么是管道4.2 管道通信的系…...

Top3专业课150满分,怎么考的?

这个系列会邀请上岸学长学姐进行经验分享~ 今天经验分享的同学是小马哥上海交大819的全程班学员&#xff0c;专业课150分满分&#xff0c;这位同学也是819期末考试的第一名&#xff0c;非常厉害&#xff01;大家吸吸欧气&#xff01; 初试成绩单 前言 先介绍下自己&#xff0…...

Windows Presentation Foundation(WPF)要点总结

Windows Presentation Foundation&#xff08;WPF&#xff09;是微软推出的一种用于构建Windows桌面应用程序的框架。自从WPF在.NET Framework 3.0中引入以来&#xff0c;它以其强大的功能和灵活性&#xff0c;逐渐成为开发人员构建现代、富用户界面应用程序的首选。本文将概述…...

【研发日记】嵌入式处理器技能解锁(一)——多任务异步执行调度的三种方法

文章目录 前言 Timer中断调度 Event中断调度 StateFlow调度 分析和应用 总结 参考资料 前言 近期在一些嵌入式系统开发项目中&#xff0c;在使用嵌入式处理器时&#xff0c;遇到了挺多费时费力的事情。所以利用晚上和周末时间&#xff0c;在这些方面深入研究了一下&…...

揭秘Python的魔法:装饰器的超能力大揭秘 ‍♂️✨

文章目录 Python进阶之装饰器详解1. 引言装饰器的概念与意义装饰器在Python编程中的作用 2. 背景介绍2.1 函数作为对象2.2 高阶函数 3. 装饰器基础3.1 理解装饰器3.2 装饰器的工作原理 4. 带参数的装饰器4.1 为什么需要带参数4.2 实现带参数的装饰器使用函数包裹装饰器使用类实…...

怎么一键消除路人?教你三个消除方法

怎么一键消除路人&#xff1f;在数字时代&#xff0c;摄影已成为我们记录生活、表达情感的重要方式。然而&#xff0c;完美的照片背后往往隐藏着一些不那么完美的元素——比如那些不经意间闯入镜头的路人。他们或许只是匆匆过客&#xff0c;但却足以破坏你精心构图的美好瞬间。…...

Android Settings系统属性读写

Settings系统属性存储均为xml&#xff0c;分三种&#xff1a; 1.global&#xff1a;所有的偏好设置对系统的所有用户公开&#xff0c;第三方APP有读没有写的权限&#xff1b; 源码地址&#xff1a;frameworks/base/core/java/android/provider/Settings.java 对应xml路径&…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

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

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

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...