【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 = val
        self.left = left
        self.right = right

# 前序遍历-递归-LC144_二叉树的前序遍历
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []

        def dfs(node):
            if node is None:
                return

            res.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:
                return

            dfs(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:
                return

            dfs(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:
                return

            if 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


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/732609.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【仿真建模-anylogic】Network代码解析

Author:赵志乾 Date:2024-06-22 Declaration:All Right Reserved!!! 1. 类图 2. 代码解析 //************************核心字段************************* // Network所属的level private transient Leve…

FFmpeg+javacpp+javacv使用

FFmpegjavacppjavacv使用 Bytedeco官网案例1、导入opencv、ffmpeg依赖包2、FFmpeg 数据结构2.1 AVFormatContext 格式化I/O上下文2.1.1 metadata2.1.2 Duration、start、bitrate等其他信息2.1.3 dump信息 Bytedeco GitHub:javacpp Bytedeco官网案例 FFmpeg – [示例…

Flutter图像编辑器应用:创造生动美丽的照片体验

介绍 引言 想象一下,在一个阳光明媚的下午,与家人或朋友漫步在风景如画的街道上。拿出手机,迫不及待地捕捉这一刻的美好,按下快门,留下了一张充满回忆的照片。 然而,回到家后发现照片的亮度有些偏暗&…

【机器学习】正则卷积群理论及Python代码实现

1. 引言 1.1.卷积神经网络CNN 卷积神经网络(CNN)的数学模型是深度学习中用于处理图像和其他高维数据的关键组成部分。那么,CNN究竟是什么呢? 总结起来,CNN网络主要完成以下操作: 卷积操作(Co…

Android记录3--ExpandableListView使用+获取SIM卡状态信息

布局文件&#xff1a; /SIM_Card_Demo/res/layout/inbox.xml <LinearLayout xmlns:android“http://schemas.android.com/apk/res/android” xmlns:tools“http://schemas.android.com/tools” android:layout_width“match_parent” android:layout_height“match_par…

Docker部署Nginx1.21.5(保姆级图文教程)

系列文章目录 Docker部署Nginx1.21.5&#xff08;保姆级图文教程&#xff09; Docker部署MySQL8.3.0&#xff08;保姆级图文教程&#xff09; 文章目录 一、环境二、拉取镜像2.1 查找 Docker Hub 上的 nginx 镜像2.2 拉取Nginx镜像2.3 查看Nginx镜像 三、在宿主机创建目录四、启…

Python爬虫基础以及示例讲解

爬虫简介 网络爬虫 爬虫指在使用程序模拟浏览器向服务端发出网络请求&#xff0c;以便获取服务端返回的内容。 但这些内容可能涉及到一些机密信息&#xff0c;所以爬虫领域目前来讲是属于灰色领域&#xff0c;切勿违法犯罪。 爬虫本身作为一门技术没有任何问题&#xff0c;关…

【FreeRTOS】创建任务_使用任务参数

参考《FreeRTOS入门与工程实践(基于DshanMCU-103).pdf》 文章目录 前言编写任务函数创建任务任务保护措施写了个bug疑问遗留问题效果freertos.c 学习链接 前言 配套源码&#xff1a;06_create_task_use_params 我们创建3个任务&#xff0c;使用同一个函数&#xff0c;但是在L…

Master PDF Editor v5 解锁版安装教程(小巧多功能PDF )

前言 Master PDF Editor&#xff0c;小巧的多功能PDF编辑器&#xff0c;轻松查看&#xff0c;创建&#xff0c;修改&#xff0c;批注&#xff0c;签名&#xff0c;扫描&#xff0c;OCR和打印PDF文档。高级注释工具&#xff0c;可以添加任意便笺指示对象突出显示&#xff0c;加…

c++中从父类继承的属性在子类内存中如何显示?

目录 一、继承概念 二、示例 三、结论 一、继承概念 在C中&#xff0c;继承是面向对象编程的一个重要特性&#xff0c;它允许一个类&#xff08;称为派生类或子类&#xff09;继承另一个类&#xff08;称为基类或父类&#xff09;的成员&#xff08;包括数据成员和成员函数…

数据结构:为什么说链表是顺序表的升级版(c语言实现)

前言&#xff1a; 我们在之前的几篇文章中详细的讲解了顺序表的特点&#xff0c;增删改查操作和动态顺序表的优点&#xff0c;并使用顺序表的底层结构实现了通讯录项目&#xff0c;似乎顺序表是一个非常完美的数据结构&#xff0c;它可以实现按照需求实现增删查改&#xff0c;对…

由于bug造成truncate table卡住问题

客户反应truncate table卡主&#xff0c;检查awr发现多个truncate在awr报告期内一直没执行完&#xff0c;如下&#xff1a; 检查ash&#xff0c;truncate table表的等待事件都是“enq: RO - fast object reuse”和“local write wait” 查找“enq: RO - fast object reuse”&am…

2024年能源电力行业CRM研究报告

中国能源电力行业属于大制造业的重要组成部分&#xff0c;在国民经济中的地位举足轻重。据统计&#xff0c;近十年来能源电力行业的整体投资呈现出增长趋势&#xff0c;尤其是“十四五”期间增长显著&#xff0c;2022年全国主要电力企业共完成投资12470亿元&#xff0c;同比增长…

Nuxt3 [Vue warn]: Hydration node mismatch:【解决方案】

[Vue warn]: Hydration node mismatch: 水合节点不匹配 Server rendered element contains more child nodes than client vdom. 服务器呈现的元素包含的子节点多于客户端vdom。 这个问题解决起来也很好解决&#xff0c;看这个问题是怎么出来的&#xff0c;看代码&#xff1a;…

vs工程添加属性表

一、简介 1、 vs工程属性表以&#xff08;.props&#xff09;为后缀 2、 作用&#xff1a;当多个工程需要配置很多相同的属性配置时方便同步&#xff0c;比如多个工程需要链接相同的头文件&#xff0c;库文件&#xff0c;输出路径&#xff0c;中间目录等 3、本章内容测试环境&a…

Mybatis框架的缓存

Mybatis框架的缓存 一.为什么使用缓存 缓存(cache&#xff09;的作用是为了减去数据库的压力&#xff0c;提高查询性能。缓存实现的 原理是从数据库中查询出来的对象在使用完后不要销毁&#xff0c;而是存储在内存&#xff08;缓存&#xff09; 中&#xff0c;当再次需要获取…

做好海外ASO优化的7大核心要素你了解几个?

海外App进行ASO优化时&#xff0c;需要综合考虑多个方面以确保应用在应用商店中获得更高的曝光率和下载量。以下是一些关键的ASO优化步骤&#xff0c;结合参考文章中的相关信息进行详细阐述&#xff1a; 1.关键词优化 调研目标市场的用户行为和检索习惯&#xff0c;挖掘与应用…

Java和C语言中基础概念中的区别有哪些?

Java和C语言中基础概念中的区别有哪些&#xff1f; 标识符数据类型运算符加号%号& 和 | 关系表达式函数声明代码规范数组 以下是Java和C语言在一些基础概念中的区别&#xff08;不包含面向对象等的高级知识&#xff09; 标识符 在Java中&#xff0c;标识符可以由数字、字母…

opencv中文路径问题

目的 在windows系统上&#xff0c;就是直接用QT的utf8编码作为图片路径用在opencv读取或者写入函数&#xff0c;在路径当中含有中文时&#xff0c;会提示编码错误。 就是解决opencv中的中文路径的问题。 情况 代码如下&#xff1a; #pragma execution_character_set("…

Ubuntu系统通过GRUB引导菜单进入恢复模式修改账户密码

当在Ubuntu系统中忘记了账户密码时&#xff0c;有几种方法可以破解或重置密码。 本指引文档方法&#xff1a;通过GRUB引导菜单进入恢复模式 实践环境为&#xff1a;20.04.6 LTS (Focal Fossa) 1. 重启Ubuntu系统&#xff1a;首先&#xff0c;你需要重启你的Ubuntu系统。 2. …