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

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.…...

泰州榉之乡全托机构探讨:自闭症并非家庭的 “末日”

当提及自闭症时&#xff0c;很多人会担忧地问&#xff1a;自闭症对家庭来说是毁灭性的吗&#xff1f;今天&#xff0c;泰州榉之乡全托机构就来为大家解开这个疑问。 榉之乡大龄自闭症托养机构在江苏、广东、江西等地都有分校&#xff0c;一直致力于为大龄自闭症患者提供专业的支…...

BiGRU:双向门控循环单元在序列处理中的深度探索

一、引言 在当今的人工智能领域&#xff0c;序列数据的处理是一个极为重要的任务&#xff0c;涵盖了自然语言处理、语音识别、时间序列分析等多个关键领域。循环神经网络&#xff08;RNN&#xff09;及其衍生结构在处理序列数据方面发挥了重要作用。然而&#xff0c;传统的 RN…...

【vue-router】Vue-router如何实现路由懒加载

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

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. 什么是幻读&#xff1f; 幻读是一种数据库事务中可能出现的并发问题&#xff0c;具体表现为&#xff1a;在同一个事务中&#xff0c;前后两次查询的结果集不同&#xff0c;仿佛“幻影”一般&#xff0c;出现了原本不存在的数据。 1.1 具体表现&#xff1a; 现象描述 事务 A…...

AI后端工程师面试题的内容

AI后端工程师面试题主要包括以下几个方面的内容‌&#xff1a; ‌一、技术基础和项目经验‌&#xff1a; ‌1. 微服务架构的理解和应用‌&#xff1a;请描述你对微服务架构的理解&#xff0c;并举例说明一个你参与过的微服务项目&#xff0c;阐述你在该项目中扮演的角色和所承…...

MFC工控项目实例三十五读取数据库数据

点击按钮打开文件夹中的数据文件生成曲线 相关代码 void CSEAL_PRESSUREDlg::OnTesReport() {CFileDialog dlgOpen(TRUE/*TRUE打开&#xff0c;FALSE保存*/,0,0,OFN_NOCHANGEDIR|OFN_FILEMUSTEXIST,"All Files(mdb.*)|*.*||",//文件过滤器NULL);CString mdb_1, m…...

OpenWrt -制作ubifs文件系统的固件

目的 创建一个ubifs为文件系统的镜像 将backup目录中的内容打包成ubifs文件系统。 ubifs的分区定义 ubi-backup.cfg 文件内容如下&#xff0c; [backup] modeubi imagenand-ipq6018-single.img vol_id0 vol_typedynamic vol_namebackup [bkver] modeubi imagebackup.ubifs v…...

C++ - 继承

继承的基本概念 继承就是一种代码的复用. 子类通过继承父类, 就能使用父类的变量, 方法. 学生和老师这两种身份, 他们都有共同的属性: 他们都有名称, 年龄, 性别 .... 当然他们也有各种独有的属性, 学生有学号, 老师有工号 .... 对于这些共有的属性, 我们可以将它们提取出来: …...

华为服务器使用U盘重装系统

一、准备工作 下载官方系统&#xff08;注意服务器CPU的架构是x86-64还是aarch64&#xff0c;不然可能报意想不到的错&#xff09;制作启动U盘&#xff08;下载rufus制作工具&#xff0c;注意文件系统选FAT32还是NTFS&#xff09; 二、安装步骤 将U盘插入USB接口重启服务器…...

网络分层模型( OSI、TCP/IP、五层协议)

1、网络分层模型 计算机网络是一个极其复杂的系统。想象一下最简单的情况&#xff1a;两台连接在网络上的计算机需要相互传输文件。不仅需要确保存在一条传输数据的通路&#xff0c;还需要完成以下几项工作&#xff1a; 发起通信的计算机必须激活数据通路&#xff0c;这包括发…...

前端开发 之 15个页面加载特效上【附完整源码】

文章目录 一&#xff1a;彩球环绕加载特效1.效果展示2.HTML完整代码 二&#xff1a;跷跷板加载特效1.效果展示2.HTML完整代码 三&#xff1a;两个圆形加载特效1.效果展示2.HTML完整代码 四&#xff1a;半环加载特效1.效果展示2.HTML完整代码 五&#xff1a;音乐波动加载特效1.效…...

Spring Boot使用JDK 21虚拟线程

JDK 21引入的虚拟线程&#xff08;Virtual Threads&#xff09;是 Project Loom 的一部分&#xff0c;旨在显著简化并发编程并提高 Java 应用的可扩展性。以下是虚拟线程的主要特点&#xff1a; 1. 概念 虚拟线程是轻量级线程&#xff0c;与传统的操作系统线程不同&#xff0…...

《从0到1常用Map集合核心摘要 + 不深不浅底层核心》

《从0到1常用Map集合核心摘要不深不浅底层核心》 前置知识 什么是键值对 ​ 键值对是一种数据结构&#xff0c;键是唯一标识&#xff0c;值是对应数据&#xff0c;用来快速查找信息。例&#xff1a; {"name": "Alice"}&#xff0c;键是name&#xff0c;…...

12 设计模式之工厂方法模式

一、什么是工厂方法模式&#xff1f; 1.定义 在软件开发中&#xff0c;设计模式 是解决常见软件设计问题的最佳实践。而 工厂方法模式&#xff08;Factory Method Pattern&#xff09; 作为创建型设计模式之一&#xff0c;常常被用来解决对象创建问题。它通过将对象的创建交给…...

spaCy 入门与实战:强大的自然语言处理库

spaCy 入门与实战&#xff1a;强大的自然语言处理库 spaCy 是一个现代化、工业级的自然语言处理&#xff08;NLP&#xff09;库&#xff0c;以高效、易用和功能丰富著称。它被广泛应用于文本处理、信息提取和机器学习任务中。本文将介绍 spaCy 的核心功能&#xff0c;并通过一…...

python包的管理和安装——笔记

1.列出包 pip list pip freeze 用这2个可以查看当前python 下所有的包和版本&#xff0c;还有下载地址 如果只是想导出当前的环境 可以用 2.安装pipreqs pip install pipreqs&#xff0c;pipreqs ./可以导出当前项目的包这个包 遇到编码报错 pipreqs ./ --encodingutf8 p…...

Vue前端页面内嵌套本项目iframe窗口的通信传输方式

一、目的 想要在iframe中使用本项目页面、并能够与其父页面组件实现实时通信。Vue前端页面内嵌套本项目iframe窗口的通信传输方式-星林社区 https://www.jl1mall.com/forum/PostDetail?postId20241202172800023969 二、iframe通信方式 1.接收消息 页面需要监听 message 事件…...

【WEB开发.js】addEventListener事件监听器的绑定和执行次数的问题(小心踩坑)

假设我们有一个按钮&#xff0c;用户点击该按钮后&#xff0c;会选择一个文件&#xff0c;且我们希望每次点击按钮时只触发一次文件处理。下面我会给你一个简单的例子&#xff0c;展示放在函数内部和放在函数外部的区别。 1. 将事件监听器放在函数内部&#xff08;问题的根源&…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...