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

【CV炼丹师勇闯力扣训练营 Day13:§6二叉树1】

CV炼丹师勇闯力扣训练营

代码随想录算法训练营第13天
二叉树的递归遍历
二叉树的迭代遍历、统一迭代
二叉树的层序遍历


一、二叉树的递归遍历(深度优先搜索)

【递归步骤】
1.确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2.确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。
3.确定单层递归的逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程

代码如下(Python):二叉树的前/中/后序遍历

from typing import List# Definition for a binary tree node.
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right# 前序遍历-递归-LC144_二叉树的前序遍历
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# 中序遍历-递归-LC94_二叉树的中序遍历
class Solution2: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# 后序遍历-递归-LC145_二叉树的后序遍历
class Solution3: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"""  [1,2,4,5,3]1/ \2   3/ \4   5
"""
# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)# 实例化Solution并进行前序遍历
solution = Solution()
result = solution.preorderTraversal(root)# 打印前序遍历的结果
print(result)

二、二叉树的迭代遍历

三、二叉树的统一迭代

# Todo

四、二叉树的层序遍历(广度优先搜索)

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现,队列先进先出,符合一层一层遍历的逻辑,而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历,只不过我们应用在二叉树上。

从左到右遍历层序遍历二叉树动画如图:

代码如下(Python)

"""
利用长度法
"""
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root:return []queue = collections.deque([root])result = []while queue:level = []for _ in range(len(queue)):cur = queue.popleft()level.append(cur.val)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)result.append(level)return result"""
递归法
"""
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root:return []levels = []def traverse(node, level):if not node:returnif len(levels) == level:levels.append([])levels[level].append(node.val)traverse(node.left, level + 1)traverse(node.right, level + 1)traverse(root, 0)return levels

相关文章:

【CV炼丹师勇闯力扣训练营 Day13:§6二叉树1】

CV炼丹师勇闯力扣训练营 代码随想录算法训练营第13天 二叉树的递归遍历 二叉树的迭代遍历、统一迭代 二叉树的层序遍历 一、二叉树的递归遍历(深度优先搜索) 【递归步骤】 1.确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理…...

代码随想录算法训练营第46天 [ 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 123.买卖股票的最佳时机III ]

代码随想录算法训练营第46天 [ 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 123.买卖股票的最佳时机III ] 一、121. 买卖股票的最佳时机 链接: 代码随想录. 思路:dp[i][0] 第i天持有股票的最大利润 dp[i][1] 第i天不持有股票的最大利润 做题状态:…...

基于IDEA的Maven简单工程创建及结构分析

目录 一、用 mvn 命令创建项目 二、用 IDEA 的方式来创建 Maven 项目。 (1)首先在 IDEA 下的 Maven 配置要已经确保完成。 (2)第二步去 new 一个 project (创建一个新工程) (3)…...

解锁空间数据奥秘:ArcGIS Pro与Python双剑合璧,处理表格数据、矢量数据、栅格数据、点云数据、GPS数据、多维数据以及遥感云平台数据等

ArcGISPro提供了用户友好的图形界面,适合初学者快速上手进行数据处理和分析。它拥有丰富的工具和功能,支持各种数据格式的处理和分析,适用于各种规模的数据处理任务。ArcGISPro在地理信息系统(GIS)领域拥有广泛的应用&…...

后端路线指导(4):后端春招秋招经验分享

后端春招&秋招经验分享 春招(暑期实习) /秋招是应届生非常重要的应聘时间,每一个想就业的同学一定要有所了解! 本篇内容,老白将与大家分享暑期实习和秋招如何应对招聘的个人经验,希望每个同学看完都能有所收获! 首先说明一下老白对于面试核心竞争力的…...

面完小红书算法岗,心态崩了。。。

暑期实习基本结束了,校招即将开启。 不同以往的是,当前职场环境已不再是那个双向奔赴时代了。求职者在变多,HC 在变少,岗位要求还更高了。提前准备才是完全之策。 最近,我们又陆续整理了很多大厂的面试题&#xff0c…...

Android 断点续传进阶之多线程下载

今天继续下载的风骚走位内容—多线程多文件断点续传 Android 断点续传基础之单线程下载:http://blog.csdn.net/qq_27489007/article/details/53897653 效果图: 文件关系: 所需内容 多文件下载列表的显示 启动多个线程分段下载 使用通知栏…...

Python爬虫学习 | Scrapy框架详解

一.Scrapy框架简介 何为框架,就相当于一个封装了很多功能的结构体,它帮我们把主要的结构给搭建好了,我们只需往骨架里添加内容就行。scrapy框架是一个为了爬取网站数据,提取数据的框架,我们熟知爬虫总共有四大部分&am…...

用户态协议栈05—架构优化

优化部分 添加了in和out两个环形缓冲区&#xff0c;收到数据包后添加到in队列&#xff1b;经过消费者线程处理之后&#xff0c;将需要发送的数据包添加到out队列。添加数据包解析线程&#xff08;消费者线程&#xff09;&#xff0c;架构分层 #include <rte_eal.h> #inc…...

模拟退火算法

模拟退火算法&#xff08;Simulated Annealing, SA&#xff09;是一种用于全局优化问题的概率搜索算法&#xff0c;其灵感来自于金属退火过程。在金属退火中&#xff0c;材料被加热到高温&#xff0c;然后缓慢冷却&#xff0c;以减少其晶格中的缺陷并达到最小能量状态。模拟退火…...

Java匿名类

Java 匿名类是一种特殊的内部类&#xff0c;它没有名字&#xff0c;并且通常用来简化代码实现&#xff0c;尤其是在实现接口或者抽象类的实例时。匿名类可以在实例化时定义其行为&#xff0c;而不需要创建单独的类文件。 匿名类的特点 没有名字&#xff1a;匿名类是没有名字的…...

G7易流赋能化工物流,实现安全、环保与效率的共赢

近日&#xff0c;中国物流与采购联合会在古都西安举办了备受瞩目的第七届化工物流安全环保发展论坛。以"坚守安全底线&#xff0c;追求绿色发展&#xff0c;智能规划化工物流未来"为主题&#xff0c;该论坛吸引了众多政府部门、行业专家和企业代表的参与。G7易流作为…...

y=sin(2x)

函数 \( y \sin(2x) \) 是一个正弦函数&#xff0c;其中 \( x \) 是自变量&#xff0c;\( y \) 是因变量。这个函数描述了一个周期性波动的波形&#xff0c;其特点是&#xff1a; 1. **振幅**&#xff1a;正弦函数的振幅是 1&#xff0c;这意味着波形在 \( y \) 轴上的最大值…...

快捷方式(lnk)--加载HTA-CS上线

免责声明:本文仅做技术交流与学习... 目录 CS: HTA文档 文件托管 借助mshta.exe突破 本地生成lnk快捷方式: 非系统图标路径不同问题: 关于lnk的上线问题: CS: HTA文档 配置监听器 有效载荷---->HTA文档--->选择监听器--->选择powershell模式----> 默认生成一…...

从同—视角理解扩散模型(Understanding Diffusion Models A Unified Perspective)

从同—视角理解扩散模型 Understanding Diffusion Models A Unified Perspective【全公式推导】【免费视频讲解】 B站视频讲解 视频的论文笔记 从同一视角理解扩散模型【视频讲解笔记】 配合视频讲解的同步笔记。 整个系列完整的论文笔记内容如下&#xff0c;仅为了不用—一回复…...

docker 基本用法及跨平台使用

一、Docker的优点 docker 主要解决的问题就是程序开发过程中编译和部署中遇到的环境配置的问题。 1.1 Docker与其他虚拟机层次结构的区别** 运行程序重点关注点在于环境。 VM虚拟机是基于Hypervisor虚拟化服务运行的。 Docker是基于内核的虚拟化技术实现的。 1.2 Docker的技…...

Vscode远程ubuntu

远程连接 到这里vscode远程到ubuntu和关闭远程连接&#xff0c;已完成 配置python环境 在远程目录下新建.vscode隐藏文件夹&#xff0c;文件夹里新建一个 settings.json 文件&#xff0c; 先远程服务器看下conda下的python虚拟环境位置 settings.json位置及内容如下 测试pyt…...

SHA256 安全散列算法加速器实验

1、SHA256 介绍 SHA256 加速器是用来计算 SHA-256 的计算单元&#xff0c; SHA256 是 SHA-2 下细分出的一种算法。 SHA-2 名称来自于安全散列算法 2 &#xff08;英语&#xff1a; Secure Hash Algorithm 2 &#xff09;的缩写&#xff0c;一种密码散列函 数算法标准…...

Elasticsearch-ES查询单字段去重

ES 语句 整体数据 GET wkl_test/_search {"query": {"match_all": {}} }结果&#xff1a; {"took" : 123,"timed_out" : false,"_shards" : {"total" : 1,"successful" : 1,"skipped" : 0…...

【Apache Doris】周FAQ集锦:第 7 期

【Apache Doris】周FAQ集锦&#xff1a;第 7 期 SQL问题数据操作问题运维常见问题其它问题关于社区 欢迎查阅本周的 Apache Doris 社区 FAQ 栏目&#xff01; 在这个栏目中&#xff0c;每周将筛选社区反馈的热门问题和话题&#xff0c;重点回答并进行深入探讨。旨在为广大用户和…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

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

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

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...

[QMT量化交易小白入门]-六十二、ETF轮动中简单的评分算法如何获取历史年化收益32.7%

本专栏主要是介绍QMT的基础用法,常见函数,写策略的方法,也会分享一些量化交易的思路,大概会写100篇左右。 QMT的相关资料较少,在使用过程中不断的摸索,遇到了一些问题,记录下来和大家一起沟通,共同进步。 文章目录 相关阅读1. 策略概述2. 趋势评分模块3 代码解析4 木头…...