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

二叉树前中后层次遍历,递归实现

文章目录

    • 前序遍历
      • 代码\Python
      • 代码\C++
    • 中序遍历
      • 代码\Python
      • 代码\C++
    • 后序遍历
      • 代码\Python
      • 代码\C++
    • 层序遍历
      • 代码\Python
      • 代码\C++
    • 反向层序遍历
      • 代码\Python
      • 代码\C++
    • 总结

前序遍历

题目链接
  前序遍历意思就是按照“根节点-左子树-右子树”的顺序来遍历二叉树,通过递归方法来实现的话很简单,我们只需要描述一下访问的规则:

1.如果当前节点为空,就返回
2.否则就访问当前节点,
3.访问左子树(左节点)
4.访问右子树(右节点)

  对python来说,一般我们用一个列表来保存访问的结果,列表对象是可修改对象,所以我们可以直接把列表对象当做函数的参数跟着传递;对C++来说,我们可以用一个vector向量来保存结果,在函数传递时使用传引用的方式,一样可以达到效果。

代码\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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []self.preorder(root, res)return resdef preorder(self, root, res):if not root:returnres.append(root.val)self.preorder(root.left, res)self.preorder(root.right, res)

代码\C++

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;travel(root, res);return res;}void travel(TreeNode *root, vector<int> &res){if(!root){return;}res.push_back(root->val);travel(root->left, res);travel(root->right, res);}
};

中序遍历

题目链接
  类似的,中序遍历就是遍历的时候把根节点放到中间,即“左子树-根节点-右子树”的顺序。只需要稍微修改一下代码就行。

代码\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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []self.inorder(res, root)return resdef inorder(self, res, root):if root is None:returnself.inorder(res, root.left)res.append(root.val)self.inorder(res, root.right)

代码\C++

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;inorder(root, res);return res;}void inorder(TreeNode *root, vector<int> &res){if(!root){return;}inorder(root->left, res);res.push_back(root->val);inorder(root->right, res);}
};

后序遍历

添加链接描述
  类似的,后序遍历就是遍历的时候把根节点放到最后,即“左子树-右子树-根节点”的顺序。同样只需要稍微修改一下代码就行。

代码\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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []self.postorder(res, root)return resdef postorder(self, res, root):if root is None:returnself.postorder(res, root.left)self.postorder(res, root.right)res.append(root.val)

代码\C++

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;postorder(root, res);return res;}void postorder(TreeNode *root, vector<int> &res){if(!root){return;}postorder(root->left, res);postorder(root->right, res);res.push_back(root->val);}
};

层序遍历

题目链接
  层序遍历一般指对二叉树进行从上到下从左到右的一层一层的遍历,同样深度的节点在同一层。递归的层序遍历需要借助节点所在的深度信息。

代码\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]]:res = []self.level(root, 0, res)return resdef level(self, root, depth, res):if not root:return []if len(res) == depth:res.append([])res[depth].append(root.val)if root.left:self.level(root.left, depth + 1, res)if root.right:self.level(root.right, depth + 1, res)

代码\C++

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;travel(root, 0, res);return res;}void travel(TreeNode *root, int depth, vector<vector<int>> &res){if(!root){return;}if(res.size() == depth){res.push_back({});}res[depth].push_back(root->val);if(root->left){travel(root->left, depth + 1, res);}if(root->right){travel(root->right, depth + 1, res);}}
};

反向层序遍历

  反向层序遍历,顾名思义就是从下往上,从左往右的反着来,我们只需要在正向遍历的基础上,在最后返回答案前把答案反转一遍。

代码\Python


return res[::-1]
#or
return res.reverse()

代码\C++

reverse(res.begin(), res.end()); 
return res;

总结

  最常见最基础的4种二叉树的遍历方式,也是二叉树很多题目的基础算法,如果对你有帮助的话,动动手指点个赞吧!

相关文章:

二叉树前中后层次遍历,递归实现

文章目录前序遍历代码\Python代码\C中序遍历代码\Python代码\C后序遍历代码\Python代码\C层序遍历代码\Python代码\C反向层序遍历代码\Python代码\C总结前序遍历 题目链接   前序遍历意思就是按照“根节点-左子树-右子树”的顺序来遍历二叉树&#xff0c;通过递归方法来实现…...

【RA4M2系列开发板GPIO体验2按键控制LED】

【RA4M2系列开发板GPIO体验2按键控制LED】1. 前言2. 配置工程2.1 新建FSP项目2.2 硬件连接以及FSP配置2.2.1 硬件连接2.2.2 FSP配置3. 软件实现3.1 实现的功能3.2 FreeRTOS使用3.2.1 Stack分配函数3.2.2 LED任务3.2.3 Key任务3.3 程序设计3.3.1 设置输出hex文件3.3.2 编译3.3.3…...

初步介绍CUDA中的统一内存

初步介绍CUDA中的统一内存 更多精彩内容: https://www.nvidia.cn/gtc-global/?ncidref-dev-876561 文章目录初步介绍CUDA中的统一内存为此&#xff0c;我向您介绍了统一内存&#xff0c;它可以非常轻松地分配和访问可由系统中任何处理器、CPU 或 GPU 上运行的代码使用的数据。…...

UVM实战--加法器

前言 这里以UVM实战&#xff08;张强&#xff09;第二章为基础修改原有的DUT&#xff0c;将DUT修改为加法器&#xff0c;从而修改代码以使得更加深入的了解各个组件的类型和使用。 一. 组件的基本框架 和第二章的平台的主要区别点 &#xff08;1&#xff09;有两个transactio…...

Linux系统点亮LED

目录应用层操控硬件的两种方式sysfs 文件系统sysfs 与/sys总结标准接口与非标准接口LED 硬件控制方式编写LED 应用程序在开发板上测试对于一款学习型开发板来说&#xff0c;永远都绕不开LED 这个小小的设备&#xff0c;基本上每块板子都至少会有一颗 LED 小灯&#xff0c;对于我…...

在superset中快速制作报表或仪表盘

在中小型企业&#xff0c;当下需要快速迭代、快速了解运营效果的业务&#xff0c;急需一款开源、好用、能快速迭代生产的报表系统。 老板很关心&#xff0c;BI工程师很关心&#xff0c;同时系统开发人员也同样关心&#xff0c;一个好的技术选型往往能够帮助公司减少很多成本&a…...

【可视化实战】Python 绘制出来的数据大屏真的太惊艳了

今天我们在进行一个Python数据可视化的实战练习&#xff0c;用到的模块叫做Panel&#xff0c;我们通过调用此模块来绘制动态可交互的图表以及数据大屏的制作。 而本地需要用到的数据集&#xff0c;可在kaggle上面获取 https://www.kaggle.com/datasets/rtatman/188-million-us…...

Obsidium一键编码作业,Obsidia惊人属性

Obsidium一键编码作业,Obsidia惊人属性 每个区域都包含几个可定制的功能&#xff0c;允许用户确定如何完全执行应用程序的安全性。Obsidia的功能区允许用户存储任何调整或一键编码作业。 Obsidia惊人属性&#xff1a; 代码虚拟化&#xff1a;代码虚拟化允许您转换程序代码的特定…...

约束优化:约束优化的三种序列无约束优化方法

文章目录约束优化&#xff1a;约束优化的三种序列无约束优化方法外点罚函数法L2-罚函数法&#xff1a;非精确算法对于等式约束对于不等式约束L1-罚函数法&#xff1a;精确算法内点罚函数法&#xff1a;障碍函数法等式约束优化问题的拉格朗日函数法&#xff1a;Uzawas Method fo…...

RocketMQ快速入门:消息发送、延迟消息、消费重试

一起学编程&#xff0c;让生活更随和&#xff01; 如果你觉得是个同道中人&#xff0c;欢迎关注博主gzh&#xff1a;【随和的皮蛋桑】。 专注于Java基础、进阶、面试以及计算机基础知识分享&#x1f433;。偶尔认知思考、日常水文&#x1f40c;。 目录1、RocketMQ消息结构1.1…...

FANUC机器人通过KAREL程序实现与PLC位置坐标通信的具体方法示例

FANUC机器人通过KAREL程序实现与PLC位置坐标通信的具体方法示例 在通信IO点位数量足够的情况下,可以使用机器人的IO点传输位置数据,这里以传输机器人的实时位置为例进行说明。 基本流程如下图所示: 基本步骤可参考如下: 首先确认机器人控制柜已经安装了总线通信软件(例如…...

[蓝桥杯 2015 省 B] 移动距离

蓝桥杯 2015 年省赛 B 组 H 题题目描述X 星球居民小区的楼房全是一样的&#xff0c;并且按矩阵样式排列。其楼房的编号为 1,2,3,⋯ 。当排满一行时&#xff0c;从下一行相邻的楼往反方向排号。比如&#xff1a;当小区排号宽度为 6 时&#xff0c;开始情形如下&#xff1a;我们的…...

Pandas库入门仅需10分钟

数据处理的时候经常性需要整理出表格&#xff0c;在这里介绍pandas常见使用&#xff0c;目录如下&#xff1a; 数据结构导入导出文件对数据进行操作 – 增加数据&#xff08;创建数据&#xff09; – 删除数据 – 改动数据 – 查找数据 – 常用操作&#xff08;转置&#xff0…...

python的socket通信中,如何设置可以让两台主机通过外网访问?

要让两台主机通过外网进行Socket通信&#xff0c;需要在网络设置和代码实现两个方面进行相应的配置。下面是具体的步骤&#xff1a; 确认网络环境&#xff1a;首先要确保两台主机都能够通过外网访问。可以通过ping命令或者telnet命令来测试两台主机之间是否可以互相访问。 确定…...

检测数据的方法(回顾)

检测数据类型的4种方法typeofinstanceofconstructor{}.toString.call() 检测数据类型的4种方法 typeof 定义 用来检测数据类型的运算符 返回一个字符串&#xff0c;表示操作值的数据类型(7种) number&#xff0c;string&#xff0c;boolean&#xff0c;object&#xff0c;u…...

比特数据结构与算法(第三章_上)栈的概念和实现(力扣:20. 有效的括号)

一、栈&#xff08;stack&#xff09;栈的概念&#xff1a;① 栈是一种特殊的线性表&#xff0c;它只允许在固定的一端进行插入和删除元素的操作。② 进行数据插入的删除和操作的一端&#xff0c;称为栈顶 。另一端则称为 栈底 。③ 栈中的元素遵守后进先出的原则&#xff0c;即…...

JVM13 类的生命周期

1. 概述 在 Java 中数据类型分为基本数据类型和引用数据类型。基本数据类型由虚拟机预先定义&#xff0c;引用数据类型则需要进行类的加载。 按照 Java 虚拟机规范&#xff0c;从 class 文件到加载到内存中的类&#xff0c;到类卸载出内存为止&#xff0c;它的整个生命周期包…...

Docker网络模式解析

目录 前言 一、常用基本命令 &#xff08;一&#xff09;查看网络 &#xff08;二&#xff09;创建网络 &#xff08;三&#xff09;查看网络源数据 &#xff08;四&#xff09;删除网络 二、网络模式 &#xff08;一&#xff09;总体介绍 &#xff08;二&#xff09…...

游山城重庆

山城楼梯多&#xff0c;路都是上坡。 为了赶早上8点从成都到重庆的动车&#xff0c;凌晨5点半就爬起床来&#xff0c;由于昨天喝了咖啡&#xff0c;所以我将尽3点才睡觉&#xff0c;这意味着我只睡了2个多小时。起来简单休息之后&#xff0c;和朋友协商好时间就一起出门了。 …...

Vuex的创建和简单使用

Vuex 1.简介 1.1简介 1.框框里面才是Vuex state&#xff1a;状态数据action&#xff1a;处理异步mutations&#xff1a;处理同步&#xff0c;视图可以同步进行渲染1.2项目创建 1.vue create 名称 2.运行后 3.下载vuex。采用的是基于vue2的版本。 npm install vuex3 --save 4.vu…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...