L16.【LeetCode笔记】前序遍历
目录
1.知识回顾
2.题目
代码模板
3.分析
数组的初始化
malloc开辟的几种方案对比
奇怪的参数returnSize
做法
代码框架
4.代码
提交结果
5.PreOrder函数常见的错误写法
1.知识回顾
106.【C语言】数据结构之二叉树的三种递归遍历方式
2.题目
https://leetcode.cn/problems/binary-tree-preorder-traversal/
给你二叉树的根节点
root,返回它节点值的 前序 遍历。示例 1:
输入:root = [1,null,2,3]
输出:[1,2,3]
解释:
示例 2:
输入:root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出:[1,2,4,5,6,7,3,8,9]
解释:
示例 3:
输入:root = []
输出:[]
示例 4:
输入:root = [1]
输出:[1]
提示:
- 树中节点数目在范围
[0, 100]内-100 <= Node.val <= 100进阶:递归算法很简单,你可以通过迭代算法完成吗?
代码模板
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{}
3.分析
和106.【C语言】数据结构之二叉树的三种递归遍历方式文章有所不同,LeetCode函数的返回值为int*,即返回一个不带NULL的int数组
数组的初始化
注意不可以返回局部数组!就像下面这样
//......
int a[100];
return a;
//......
一旦离开preorderTraversal函数会被销毁,导致出现野指针,因此必须malloc在堆区开辟
而且LeetCode给出了提示
Note: The returned array must be malloced, assume caller calls free().
这里不用担心free的问题,假设调用者调用了free()
malloc开辟的几种方案对比
方案1.LeetCode给出了提示"树中节点数目在范围 [0, 100] 内",因此可以一次性开辟足够的空间
int* a = (int*)malloc(100*sizeof(int));
但可能会出现空间浪费的情况
方案2.先计算二叉树的大小(节点个数*每个节点所占的内存空间),再malloc
方案3.一开始开辟较小的空间,不够了再扩容
本文采用方案2,直接调用107.【C语言】数据结构之二叉树求总节点和第K层节点的个数文章的TreeSize函数
奇怪的参数returnSize
在int* preorderTraversal(struct TreeNode* root, int* returnSize)传了一个int*类型的参数returnSize,
LeetCode规定返回数组时要不仅仅要求返回首元素的地址还要返回数组的大小returnSize
由于形参的改变不影响实参,因此需要传returnSize的地址,因此为int*类型的参数
做法
return a;之前先将数组的大小传给*returnSize
代码框架
int TreeSize(struct TreeNode* root)
{return root==NULL ? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{*returnSize=TreeSize(root);int* a=(int*)malloc(*returnSize*sizeof(int));//......//遍历并写入数组//......return a;
}
4.代码
106.【C语言】数据结构之二叉树的三种递归遍历方式文章的PreOrder函数的代码
void PreOrder(BTNode* root)
{//先判断是否为空树(叶节点的左节点和右节点均为空树)if (root == NULL){printf("NULL ");return;}//按根-->左子树-->右子树的顺序遍历printf("%d ",root->data);PreOrder(root->left);PreOrder(root->right);
}
稍加改造上方PreOrder函数即可
void PreOrder(struct TreeNode* root,int* a,int* i)
{if (root==NULL)return;//写入数组a[(*i)++]=root->val;PreOrder(root->left,a,i);PreOrder(root->right,a,i);
}int TreeSize(struct TreeNode* root)
{return root==NULL ? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{*returnSize=TreeSize(root);int* a=(int*)malloc(*returnSize*sizeof(int));int i=0;PreOrder(root,a,&i);return a;
}
提交结果

如果将代码的*returnSize=TreeSize(root);注释掉会报错

5.PreOrder函数常见的错误写法
void PreOrder(struct TreeNode* root,int* a,int i)
{if (root==NULL)return;//写入数组a[i++]=root->val;PreOrder(root->left,a,i);PreOrder(root->right,a,i);
}//省略TreeSize
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{//前面内容省略PreOrder(root,a,0);//后面内容省略
}
运行结果:不完全通过

以下面这个用例分析

画递归展开图

由于CSDN会压缩图片画质,无损bmp图片(大小7.32M)链接见https://pan.baidu.com/s/1OIrE-cGvefJs_SFZ75w84w?pwd=gq37
解决方法:1.传址调用 2.使用全局变量
备注:不建议使用全局变量,LeetCode有多个测试用例会反复调用函数,导致全局变量无法清零
相关文章:
L16.【LeetCode笔记】前序遍历
目录 1.知识回顾 2.题目 代码模板 3.分析 数组的初始化 malloc开辟的几种方案对比 奇怪的参数returnSize 做法 代码框架 4.代码 提交结果 5.PreOrder函数常见的错误写法 1.知识回顾 106.【C语言】数据结构之二叉树的三种递归遍历方式 2.题目 https://leetcode.…...
泰州榉之乡全托机构探讨:自闭症并非家庭的 “末日”
当提及自闭症时,很多人会担忧地问:自闭症对家庭来说是毁灭性的吗?今天,泰州榉之乡全托机构就来为大家解开这个疑问。 榉之乡大龄自闭症托养机构在江苏、广东、江西等地都有分校,一直致力于为大龄自闭症患者提供专业的支…...
BiGRU:双向门控循环单元在序列处理中的深度探索
一、引言 在当今的人工智能领域,序列数据的处理是一个极为重要的任务,涵盖了自然语言处理、语音识别、时间序列分析等多个关键领域。循环神经网络(RNN)及其衍生结构在处理序列数据方面发挥了重要作用。然而,传统的 RN…...
【vue-router】Vue-router如何实现路由懒加载
✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,…...
Linux网络编程基础
目录 一、网络发展历史和分层 1.1Internet的历史 1.2网络的体系结构 1.2.1OSI模型 1.2.2TCP/IP协议族 1.2.3各层典型协议 1.2.4网络的封包和拆包 二、网络编程的预备知识 2.1Socket 2.1.1概念 2.1.2类型 2.2IP地址 2.3端口号 2.4字节序 一、网络发展历史和分层 …...
MySQL中的幻读问题
1. 什么是幻读? 幻读是一种数据库事务中可能出现的并发问题,具体表现为:在同一个事务中,前后两次查询的结果集不同,仿佛“幻影”一般,出现了原本不存在的数据。 1.1 具体表现: 现象描述 事务 A…...
AI后端工程师面试题的内容
AI后端工程师面试题主要包括以下几个方面的内容: 一、技术基础和项目经验: 1. 微服务架构的理解和应用:请描述你对微服务架构的理解,并举例说明一个你参与过的微服务项目,阐述你在该项目中扮演的角色和所承…...
MFC工控项目实例三十五读取数据库数据
点击按钮打开文件夹中的数据文件生成曲线 相关代码 void CSEAL_PRESSUREDlg::OnTesReport() {CFileDialog dlgOpen(TRUE/*TRUE打开,FALSE保存*/,0,0,OFN_NOCHANGEDIR|OFN_FILEMUSTEXIST,"All Files(mdb.*)|*.*||",//文件过滤器NULL);CString mdb_1, m…...
OpenWrt -制作ubifs文件系统的固件
目的 创建一个ubifs为文件系统的镜像 将backup目录中的内容打包成ubifs文件系统。 ubifs的分区定义 ubi-backup.cfg 文件内容如下, [backup] modeubi imagenand-ipq6018-single.img vol_id0 vol_typedynamic vol_namebackup [bkver] modeubi imagebackup.ubifs v…...
C++ - 继承
继承的基本概念 继承就是一种代码的复用. 子类通过继承父类, 就能使用父类的变量, 方法. 学生和老师这两种身份, 他们都有共同的属性: 他们都有名称, 年龄, 性别 .... 当然他们也有各种独有的属性, 学生有学号, 老师有工号 .... 对于这些共有的属性, 我们可以将它们提取出来: …...
华为服务器使用U盘重装系统
一、准备工作 下载官方系统(注意服务器CPU的架构是x86-64还是aarch64,不然可能报意想不到的错)制作启动U盘(下载rufus制作工具,注意文件系统选FAT32还是NTFS) 二、安装步骤 将U盘插入USB接口重启服务器…...
网络分层模型( OSI、TCP/IP、五层协议)
1、网络分层模型 计算机网络是一个极其复杂的系统。想象一下最简单的情况:两台连接在网络上的计算机需要相互传输文件。不仅需要确保存在一条传输数据的通路,还需要完成以下几项工作: 发起通信的计算机必须激活数据通路,这包括发…...
前端开发 之 15个页面加载特效上【附完整源码】
文章目录 一:彩球环绕加载特效1.效果展示2.HTML完整代码 二:跷跷板加载特效1.效果展示2.HTML完整代码 三:两个圆形加载特效1.效果展示2.HTML完整代码 四:半环加载特效1.效果展示2.HTML完整代码 五:音乐波动加载特效1.效…...
Spring Boot使用JDK 21虚拟线程
JDK 21引入的虚拟线程(Virtual Threads)是 Project Loom 的一部分,旨在显著简化并发编程并提高 Java 应用的可扩展性。以下是虚拟线程的主要特点: 1. 概念 虚拟线程是轻量级线程,与传统的操作系统线程不同࿰…...
《从0到1常用Map集合核心摘要 + 不深不浅底层核心》
《从0到1常用Map集合核心摘要不深不浅底层核心》 前置知识 什么是键值对 键值对是一种数据结构,键是唯一标识,值是对应数据,用来快速查找信息。例: {"name": "Alice"},键是name,…...
12 设计模式之工厂方法模式
一、什么是工厂方法模式? 1.定义 在软件开发中,设计模式 是解决常见软件设计问题的最佳实践。而 工厂方法模式(Factory Method Pattern) 作为创建型设计模式之一,常常被用来解决对象创建问题。它通过将对象的创建交给…...
spaCy 入门与实战:强大的自然语言处理库
spaCy 入门与实战:强大的自然语言处理库 spaCy 是一个现代化、工业级的自然语言处理(NLP)库,以高效、易用和功能丰富著称。它被广泛应用于文本处理、信息提取和机器学习任务中。本文将介绍 spaCy 的核心功能,并通过一…...
python包的管理和安装——笔记
1.列出包 pip list pip freeze 用这2个可以查看当前python 下所有的包和版本,还有下载地址 如果只是想导出当前的环境 可以用 2.安装pipreqs pip install pipreqs,pipreqs ./可以导出当前项目的包这个包 遇到编码报错 pipreqs ./ --encodingutf8 p…...
Vue前端页面内嵌套本项目iframe窗口的通信传输方式
一、目的 想要在iframe中使用本项目页面、并能够与其父页面组件实现实时通信。Vue前端页面内嵌套本项目iframe窗口的通信传输方式-星林社区 https://www.jl1mall.com/forum/PostDetail?postId20241202172800023969 二、iframe通信方式 1.接收消息 页面需要监听 message 事件…...
【WEB开发.js】addEventListener事件监听器的绑定和执行次数的问题(小心踩坑)
假设我们有一个按钮,用户点击该按钮后,会选择一个文件,且我们希望每次点击按钮时只触发一次文件处理。下面我会给你一个简单的例子,展示放在函数内部和放在函数外部的区别。 1. 将事件监听器放在函数内部(问题的根源&…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
sshd代码修改banner
sshd服务连接之后会收到字符串: SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢? 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头,…...
Netty自定义协议解析
目录 自定义协议设计 实现消息解码器 实现消息编码器 自定义消息对象 配置ChannelPipeline Netty提供了强大的编解码器抽象基类,这些基类能够帮助开发者快速实现自定义协议的解析。 自定义协议设计 在实现自定义协议解析之前,需要明确协议的具体格式。例如,一个简单的…...


