当前位置: 首页 > 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;问题的根源&…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...