C语言用递归实现二叉树的层次遍历

时间: 2023-09-03 17:13:10 浏览: 51
C语言用递归实现二叉树的层次遍历相对不太常见,但是也是可以通过递归实现的。递归实现二叉树的层次遍历需要借助队列,具体步骤如下: 1. 定义一个队列,将根节点入队; 2. 定义一个辅助函数,该函数接收一个队列作为参数,并将队列中的节点按照层次顺序出队并访问其值,同时将其左右子节点入队; 3. 调用辅助函数,开始遍历。 下面是实现代码: ```c #include <stdio.h> #include <stdlib.h> struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; void dfs(struct TreeNode* node, int depth, int **res, int *returnSize) { if (*returnSize == depth) { *res = (int *)realloc(*res, (*returnSize+1)*sizeof(int *)); (*res)[*returnSize] = node->val; (*returnSize)++; } else { (*res)[depth] = node->val; } if (node->left) { dfs(node->left, depth+1, res, returnSize); } if (node->right) { dfs(node->right, depth+1, res, returnSize); } } int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) { int **res = (int **)malloc(sizeof(int *)); *returnSize = 0; if (!root) { *returnColumnSizes = NULL; return NULL; } dfs(root, 0, &res, returnSize); *returnColumnSizes = (int *)malloc(*returnSize*sizeof(int)); for (int i = 0; i < *returnSize; i++) { (*returnColumnSizes)[i] = 1; } return res; } ``` 在辅助函数 `dfs` 中,我们传入了节点、节点所处的深度、结果列表、结果列表的大小作为参数。如果当前深度在结果列表中不存在,就在结果列表中添加一个新的空间,然后将当前节点的值加入到该列表中。接着,我们判断当前节点是否有左右子节点,如果有,就调用 `dfs` 函数遍历其子节点,并将深度加 1。最后,我们在主函数中调用 `dfs` 函数遍历根节点,并将深度初始化为 0,返回结果列表 `res` 即可。 需要注意的是,这种方法虽然可以实现二叉树的层次遍历,但是由于递归的过程中需要将每一层的节点都存入结果列表中,因此空间复杂度较高。如果二叉树深度较大,可能会导致栈溢出或者内存不足问题。因此,建议在实际应用中使用迭代的方式实现二叉树的层次遍历。

相关推荐

最新推荐

recommend-type

子比主题ACG美化插件全开源

子比主题ACG美化插件[全开源] 不要改人家原作者版权,不要用于违法乱纪
recommend-type

vgg模型-图像分类算法对大米体型识别-不含数据集图片-含逐行注释和说明文档.zip

vgg模型_图像分类算法对大米体型识别-不含数据集图片-含逐行注释和说明文档 本代码是基于python pytorch环境安装的。 下载本代码后,有个环境安装的requirement.txt文本 如果有环境安装不会的,可自行网上搜索如何安装python和pytorch,这些环境安装都是有很多教程的,简单的 环境需要自行安装,推荐安装anaconda然后再里面推荐安装python3.7或3.8的版本,pytorch推荐安装1.7.1或1.8.1版本 首先是代码的整体介绍 总共是3个py文件,十分的简便 且代码里面的每一行都是含有中文注释的,小白也能看懂代码 然后是关于数据集的介绍。 本代码是不含数据集图片的,下载本代码后需要自行搜集图片放到对应的文件夹下即可 在数据集文件夹下是我们的各个类别,这个类别不是固定的,可自行创建文件夹增加分类数据集 需要我们往每个文件夹下搜集来图片放到对应文件夹下,每个对应的文件夹里面也有一张提示图,提示图片放的位置 然后我们需要将搜集来的图片,直接放到对应的文件夹下,就可以对代码进行训练了。 运行01生成txt.py,是将数据集文件夹下
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

深入了解MATLAB开根号的最新研究和应用:获取开根号领域的最新动态

![matlab开根号](https://www.mathworks.com/discovery/image-segmentation/_jcr_content/mainParsys3/discoverysubsection_1185333930/mainParsys3/image_copy.adapt.full.medium.jpg/1712813808277.jpg) # 1. MATLAB开根号的理论基础 开根号运算在数学和科学计算中无处不在。在MATLAB中,开根号可以通过多种函数实现,包括`sqrt()`和`nthroot()`。`sqrt()`函数用于计算正实数的平方根,而`nt
recommend-type

react的函数组件的使用

React 的函数组件是一种简单的组件类型,用于定义无状态或者只读组件。 它们通常接受一个 props 对象作为参数并返回一个 React 元素。 函数组件的优点是代码简洁、易于测试和重用,并且它们使 React 应用程序的性能更加出色。 您可以使用函数组件来呈现简单的 UI 组件,例如按钮、菜单、标签或其他部件。 您还可以将它们与 React 中的其他组件类型(如类组件或 Hooks)结合使用,以实现更复杂的 UI 交互和功能。
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。
recommend-type

"互动学习:行动中的多样性与论文攻读经历"

多样性她- 事实上SCI NCES你的时间表ECOLEDO C Tora SC和NCESPOUR l’Ingén学习互动,互动学习以行动为中心的强化学习学会互动,互动学习,以行动为中心的强化学习计算机科学博士论文于2021年9月28日在Villeneuve d'Asq公开支持马修·瑟林评审团主席法布里斯·勒菲弗尔阿维尼翁大学教授论文指导奥利维尔·皮耶昆谷歌研究教授:智囊团论文联合主任菲利普·普雷教授,大学。里尔/CRISTAL/因里亚报告员奥利维耶·西格德索邦大学报告员卢多维奇·德诺耶教授,Facebook /索邦大学审查员越南圣迈IMT Atlantic高级讲师邀请弗洛里安·斯特鲁布博士,Deepmind对于那些及时看到自己错误的人...3谢谢你首先,我要感谢我的两位博士生导师Olivier和Philippe。奥利维尔,"站在巨人的肩膀上"这句话对你来说完全有意义了。从科学上讲,你知道在这篇论文的(许多)错误中,你是我可以依
recommend-type

解决MATLAB开根号常见问题:提供开根号运算的解决方案

![解决MATLAB开根号常见问题:提供开根号运算的解决方案](https://img-blog.csdnimg.cn/d939d1781acc404d8c826e8af207e68f.png) # 1. MATLAB开根号运算基础** MATLAB开根号运算用于计算一个数的平方根。其语法为: ``` y = sqrt(x) ``` 其中: * `x`:要开根号的数或数组 * `y`:开根号的结果 开根号运算的输入可以是实数、复数、矩阵或数组。对于实数,开根号运算返回一个非负实数。对于复数,开根号运算返回一个复数。对于矩阵或数组,开根号运算逐元素执行,对每个元素进行开根号运算。 #
recommend-type

inputstream

Inputstream是Java中用于从输入流中读取数据的抽象类,它是Java I/O类库中的一部分。Inputstream提供了read()和read(byte[] b)等方法,可以从输入流中读取一个字节或一组字节。在Java中,FileInputStream、ByteArrayInputStream和StringBufferInputStream都是Inputstream的子类,用于读取不同类型的输入流。