力扣589:N叉树的先序遍历

devtools/2024/11/17 2:06:05/

给定一个 n 叉树的根节点  root ,返回 其节点值的 前序遍历 。

n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。

示例 1:

输入:root = [1,null,3,2,4,null,5,6]
输出:[1,3,5,6,2,4]

示例 2:

输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

代码:

// result:用于存储节点值的整数数组指针
// i:指向一个整数的指针,用于记录当前已经存储到result数组中的元素个数,同时也作为下一个要存储元素的下标
void DFS(struct Node* root, int* result, int* i) {// 如果根节点为空,说明已经到达树的底部或者传入的就是空树,此时直接返回,不进行后续的遍历操作if (root == NULL) return;// 将当前根节点的值存储到result数组中,存储的位置由*i指定,然后将*i的值加1,以便下一次存储元素时使用下一个下标result[(*i)++]=root->val;// 遍历当前根节点的所有子节点,对每个子节点递归调用DFS函数进行深度优先搜索// root->numChildren表示当前根节点拥有的子节点个数for (int j = 0; j < root->numChildren; j++) {DFS(root->children[j], result, i);}
}// returnSize:一个指针,用于返回先序遍历结果数组的大小(即存储了多少个节点的值)
int* preorder(struct Node* root, int* returnSize) {// 为存储先序遍历结果分配足够大的内存空间,这里假设最多有10000个节点(实际应用中可能需要根据具体情况调整)int* result = (int *)malloc(sizeof(int)*10000);// 初始化先序遍历结果数组的大小为0,即还没有存储任何节点的值*returnSize = 0;// 调用DFS函数进行深度优先搜索,将先序遍历结果存储到result数组中,并通过returnSize指针更新存储的节点个数DFS(root, result, returnSize);// 返回存储先序遍历结果的数组指针,调用者可以通过这个指针访问先序遍历结果数组中的元素,记得在使用完后要释放内存return result;
}


http://www.ppmy.cn/devtools/134595.html

相关文章

SpringBoot开发——Spring Boot 3.3整合RabbitMQ构建高效稳定的消息队列系统

文章目录 一、配置 RabbitMQ二、自动配置的核心组件三、发送消息至指定 Stream四、接收消息与 RabbitListener 注解五、实现自定义 RabbitListenerContainerFactory六、消息重试机制七、总 结 消息队列在分布式系统中起着至关重要的作用&#xff0c;它能够解耦系统、削峰填谷&a…

MQTT协议解析 : 物联网领域的最佳选择

1. MQTT协议概述 1.1 MQTT协议是什么 MQTT : Message Queuing Telemetry Transport 模式 : 发布 / 订阅主题优点 : 代码量小、低带宽、实时可靠应用 : 物联网、小型设备、移动应用MQTT 常用端口 : 1883 MQTT是一个网络协议&#xff0c;和HTTP类似&#xff0c;因为轻量简单&…

UE5材质篇 4 材质表面雨滴打落

materials 101的教程的灵感&#xff0c;特此记录一下 教程里本质上其实是先实验确定了湿滑表面的roughness和specular的值metallic这些&#xff0c;然后根据time来给表面的某些点这几个属性进行变换&#xff0c;主要是roughness和normal的变化 具体的变化是依赖了一张noise&a…

k8s拓扑域 :topologyKey

主要用于定义Pod亲和性或反亲和性规则中的拓扑域&#xff0c;从而控制Pod在集群中的调度。 参数描述&#xff1a;仅支持在工作负载亲和/工作负载反亲和调度策略中使用。先圈定拓扑域&#xff08;topologyKey&#xff09;指定的范围&#xff0c;然后再选择策略定义的内容。 to…

macOS sw_vers 查看当前系统版本

macOS 命令行 查看当前系统版本 sw_vers ProductName: macOS ProductVersion: 15.1

STM32设计学生宿舍监测控制系统

目录 前言 一、本设计主要实现哪些很“开门”功能&#xff1f; 二、电路设计原理图 电路图采用Altium Designer进行设计&#xff1a; 三、实物设计图 四、程序源代码设计 五、获取资料内容 前言 随着科技的飞速发展和智能化时代的到来&#xff0c;学生宿舍的安全、舒适…

MATLAB中的绘图技巧

MATLAB作为一种强大的科学计算软件&#xff0c;不仅可以进行数据分析和模拟&#xff0c;还具有出色的绘图功能。本文介绍若干在MATLAB中绘图的技巧和方法&#xff0c;帮助使用者更好地呈现数据和结果 文章目录 基本绘图函数高级绘图技巧三维绘图动态绘图绘图工具结语 基本绘图函…

利用OpenAI进行测试需求分析——从电商网站需求到测试用例的生成

在软件测试工程师的日常工作中&#xff0c;需求分析是测试工作中的关键步骤。需求文档决定了测试覆盖的范围和测试策略&#xff0c;而测试用例的编写往往依赖于需求的准确理解。传统手工分析需求耗时长&#xff0c;尤其在面对大量需求和复杂逻辑时容易遗漏细节。本文将以电商网…