leetcode 103.二叉树的锯齿形层序遍历

1.题目要求:

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

在这里插入图片描述
2.做题思路:由题我们可以判断，树中每到偶数层时，就会逆置，所以我们可以采用层序遍历和逆置函数的方法来解此题
3.做题步骤:
1.我们先把层序遍历所需要的队列结构，出队和入队函数写好：

//创建队列
typedef struct queue{struct TreeNode* value;struct queue* next;
}queue_t;
//入队
void push(queue_t** head,struct TreeNode* data){queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));newnode->value = data;newnode->next = NULL;if(*head == NULL){*head = newnode;return;}queue_t* tail = *head;while(tail->next != NULL){tail = tail->next;}tail->next = newnode;
}
//出队
struct TreeNode* pop(queue_t** head){struct TreeNode* x = (*head)->value;(*head) = (*head)->next;return x;
}

2.写好逆置函数:

void reverse(int* number,int left,int right){while(left <= right){int temp = number[left];number[left] = number[right];number[right] = temp;left++;right--;}
}

3.写好进行层序遍历的变量:

*returnSize = 0;if(root == NULL){return NULL;}int* each_line_nodes = (int*)malloc(sizeof(int)*2000);//记录每行结点数int j_1 = 0;int* level_order_number = (int*)malloc(sizeof(int)* 2000);//层序遍历的数组int j_2 = 0;int depth = 0;//树的高度int count = 1;//根结点的个数int index = 0;//记录每层的第一个的索引int nextcount = 0;//下一个结点的个数int size = 0;//记录队列中的个数queue_t* quence = NULL;//设置队列

4.进行层序遍历:

//进行层序遍历push(&quence,root);size++;while(size != 0){depth++;for(int i = 0;i < count;i++){struct TreeNode* temp = pop(&quence);size--;level_order_number[j_2] = temp->val;j_2++;if(temp->left != NULL){push(&quence,temp->left);size++;nextcount++;}if(temp->right != NULL){push(&quence,temp->right);size++;nextcount++;}}each_line_nodes[j_1] = count;j_1++;//如果高度为偶数时，就要对数组这一次的元素进行逆置if(depth % 2 == 0){reverse(level_order_number,index,j_2 - 1);index += count;}else{index += count;}count = nextcount;nextcount = 0;}

5.再创造二维数组，把值放入二维数组中:

//设立二维数组int** array = (int**)malloc(sizeof(int*)* depth);for(int i = 0;i < depth;i++){array[i] = (int*)malloc(sizeof(int) * each_line_nodes[i]);}int f = 0;for(int i = 0;i < depth;i++){for(int j = 0;j < each_line_nodes[i];j++){array[i][j] = level_order_number[f];f++;}}*returnSize = depth;*returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));for(int i = 0;i < depth;i++){(*returnColumnSizes)[i] = each_line_nodes[i];}return array;

以下为全部代码:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*///创建队列
typedef struct queue{struct TreeNode* value;struct queue* next;
}queue_t;
//入队
void push(queue_t** head,struct TreeNode* data){queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));newnode->value = data;newnode->next = NULL;if(*head == NULL){*head = newnode;return;}queue_t* tail = *head;while(tail->next != NULL){tail = tail->next;}tail->next = newnode;
}
//出队
struct TreeNode* pop(queue_t** head){struct TreeNode* x = (*head)->value;(*head) = (*head)->next;return x;
}
void reverse(int* number,int left,int right){while(left <= right){int temp = number[left];number[left] = number[right];number[right] = temp;left++;right--;}
}
int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {*returnSize = 0;if(root == NULL){return NULL;}int* each_line_nodes = (int*)malloc(sizeof(int)*2000);//记录每行结点数int j_1 = 0;int* level_order_number = (int*)malloc(sizeof(int)* 2000);//层序遍历的数组int j_2 = 0;int depth = 0;//树的高度int count = 1;//根结点的个数int index = 0;//记录每层的第一个的索引int nextcount = 0;//下一个结点的个数int size = 0;//记录队列中的个数queue_t* quence = NULL;//设置队列//进行层序遍历push(&quence,root);size++;while(size != 0){depth++;for(int i = 0;i < count;i++){struct TreeNode* temp = pop(&quence);size--;level_order_number[j_2] = temp->val;j_2++;if(temp->left != NULL){push(&quence,temp->left);size++;nextcount++;}if(temp->right != NULL){push(&quence,temp->right);size++;nextcount++;}}each_line_nodes[j_1] = count;j_1++;//如果高度为偶数时，就要对数组这一次的元素进行逆置if(depth % 2 == 0){reverse(level_order_number,index,j_2 - 1);index += count;}else{index += count;}count = nextcount;nextcount = 0;} //设立二维数组int** array = (int**)malloc(sizeof(int*)* depth);for(int i = 0;i < depth;i++){array[i] = (int*)malloc(sizeof(int) * each_line_nodes[i]);}int f = 0;for(int i = 0;i < depth;i++){for(int j = 0;j < each_line_nodes[i];j++){array[i][j] = level_order_number[f];f++;}}*returnSize = depth;*returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));for(int i = 0;i < depth;i++){(*returnColumnSizes)[i] = each_line_nodes[i];}return array;
}

好了，这就是我的解题方法，大家如果觉得好的话，不妨给个免费的赞吧，谢谢了^ _ ^

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/396088.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

spring过滤器和拦截器的区别

spring过滤器和拦截器的区别

1出身不同。 过滤器来自servlet&#xff0c;拦截器来自spring框架。 2触发时机 不同请求的执行顺序是&#xff1a;请求进入容器 > 进入过滤器 > 进入 Servlet > 进入拦截器 > 执行控制器 过滤器先执行&#xff0c;会在servlet请求之前和相应之后进行处理。 拦…
阅读更多...
写一个Vue2和vue3的自定义指令（以复制指定作为示例）

写一个Vue2和vue3的自定义指令（以复制指定作为示例）

文章目录 一、自定义指令是什么&#xff1f;二、自定义指令有啥用&#xff1f;三、自定义指令怎么用&#xff1f;1.自定义指令的参数2.自定义指令的钩子函数&#xff08;1&#xff09;五个钩子函数的说明&#xff08;2&#xff09;钩子函数的参数(主要参数&#xff1a;el和valu…
阅读更多...
【活动预告】研讨会+开源集市，IoTDB “登录” GOTC 2024！

【活动预告】研讨会+开源集市，IoTDB “登录” GOTC 2024！

由开源中国与上海浦东软件园联合举办的 GOTC 2024 即将开幕&#xff01;本次大会结合 “GOTC&#xff08;全球开源技术峰会&#xff09;” 与 “GOGC&#xff08;全球开源极客嘉年华&#xff09;”&#xff0c;将集结全球范围内对开源技术充满热情的开发者、社区成员、创业者、…
阅读更多...
Oracle是如何保证数据不丢的

Oracle是如何保证数据不丢的

上一篇文章给大家梳理了一条更新语句在Oracle数据库中是如何执行的&#xff0c;我们也提到只要更新记录成功写入到在线重做日志文件&#xff0c;Oracle就能保证数据不会丢失。同时也向大家解释了&#xff0c;其实这个时候数据并没有写入到数据文件&#xff0c;因此这个时候仍然…
阅读更多...
为什么不用postman做自动化

为什么不用postman做自动化

面试的时候被问到&#xff1a;为什么不用postman做自动化 打开postman&#xff0c;看到用例集管理、API 管理、环境管理这三个功能&#xff0c;用户体验感算得上品牌等级了 为什么不用呢&#xff0c;文心一言给了一些答案 不适合大规模自动化测试&#xff1a;Postman 主要是为…
阅读更多...
React 后台管理项目 入门项目 简洁清晰保姆级内容讲解

React 后台管理项目 入门项目 简洁清晰保姆级内容讲解

序章 React Hook的后台管理项目&#xff0c;从0到1搭建&#xff0c;内容非常丰富涵盖项目搭建、路由配置、用户鉴权、首页报表、用户列表、前后端联调等功能&#xff0c;推荐指数&#xff1a;5颗星&#xff01; 视频学习链接: React 通用后台管理-零基础从0到1详细的入门保姆…
阅读更多...
数据结构(5.5_3)——并查集的进一步优化

数据结构(5.5_3)——并查集的进一步优化

Find操作的优化(压缩路径) 压缩路径——Find操作&#xff0c;先找到根节点&#xff0c;再将查找路径上所有结点都挂到根结点下 代码&#xff1a; //Find "查"操作优化&#xff0c;先找到根节点&#xff0c;再进行"路径压缩" int Find(int S[], int x) {…
阅读更多...
50 mysql 的 “where 1 = 1“ 的优化处理

50 mysql 的 “where 1 = 1“ 的优化处理

前言 问题是来自于 chinaunix 问题 ”mysql查询后面加 where 1 1 影响效率吗?” mysql 中在 java 代码中我们经常会使用到 ”where 1 1 and username ‘jerry’ ” 之类的条件 然后 我们这里 来看一下 “where 1 1” 的相关处理 where 条件在 select_lex, QUP_shared…
阅读更多...
LeetCode面试150——14最长公共前缀

LeetCode面试150——14最长公共前缀

题目难度&#xff1a;简单 默认优化目标&#xff1a;最小化平均时间复杂度。 Python默认为Python3。 目录 1 题目描述 2 题目解析 3 算法原理及代码实现 3.1 横向扫描 3.2 纵向扫描 3.3 分治 3.4 二分查找 参考文献 1 题目描述 编写一个函数来查找字符串数组中的最长…
阅读更多...
【面试题】设计模式-责任链模式

【面试题】设计模式-责任链模式

设计模式-责任链模式 前言责任链简历案例代码小结 前言 我们知道&#xff0c;设计模式是面试时经常被问到的问题之一&#xff0c;这是因为设计模式能够体现出代码设计的美感&#xff0c;且在很多框架的底层也都会使用到各种设计模式&#xff0c;所以对设计模式的考察&#xff…
阅读更多...
用Manim创建条形图【BarChart】

用Manim创建条形图【BarChart】

BarChart是Manim库中用于创建条形图的函数。它允许用户通过一组值创建一个条形图&#xff0c;其参数可以调整条形的外观和布局。 BarChart(values, bar_namesNone, y_rangeNone, x_lengthNone, y_lengthNone, bar_colors[#003f5c, #58508d, #bc5090, #ff6361, #ffa600],bar_w…
阅读更多...
js第四天-函数

js第四天-函数

例1&#xff1a;选出最大值&#xff1a; <script>function getmax(x, y) {return x > y ? x : y}let max getmax(1, 3)</script> 例2&#xff1a;返回数组的最大值 <script>function getArrValue(arr []) {let max arr[0]for (let i 1; i < arr.…
阅读更多...
基于Hadoop的共享单车分布式存储与计算

基于Hadoop的共享单车分布式存储与计算

文章目录 有需要本项目的代码或文档以及全部资源&#xff0c;或者部署调试可以私信博主项目介绍研究背景研究目的和意义国内外研究现状总体研究思路数据可视化每文一语 有需要本项目的代码或文档以及全部资源&#xff0c;或者部署调试可以私信博主 项目介绍 共享单车的普及带…
阅读更多...
Elastic 基于 RAG 的 AI 助手：使用 LLM 和私有 GitHub 问题分析应用程序问题

Elastic 基于 RAG 的 AI 助手：使用 LLM 和私有 GitHub 问题分析应用程序问题

作者&#xff1a;来自 Bahubali Shetti 作为 SRE&#xff0c;分析应用程序比以往任何时候都更加复杂。你不仅必须确保应用程序以最佳方式运行以确保出色的客户体验&#xff0c;而且在某些情况下还必须了解内部工作原理以帮助排除故障。分析基于生产的服务中的问题是一项团队运动…
阅读更多...
HTML “文本处理基础”--文本格式化——WEB开发系列05

HTML “文本处理基础”--文本格式化——WEB开发系列05

HTML 的主要工作之一是赋予文本结构&#xff0c;使浏览器能够按照开发者的意图显示 HTML 文档。 在创建网页时&#xff0c;文本格式化是至关重要的&#xff0c;它不仅可以影响用户的阅读体验&#xff0c;还可以增强网页的可读性和美观性。HTML 如何通过添加标题和段落、强调单词…
阅读更多...
中央空调系统

中央空调系统

1.水机 它首先通过主机将水变成7度左右的冷水&#xff08;制冷&#xff09;&#xff0c;然后通过水管通过水泵输送到房间的每一端。末端的风机盘管与室内空气进行热交换&#xff0c;达到制冷的目的。供暖也是如此&#xff0c;但主机先把水变成50度左右的热水这种空调的优点是舒…
阅读更多...
前端已经学会vue，做粒子效果

前端已经学会vue，做粒子效果

目录 1. Canvas API 2. WebGL 3. 粒子系统 4. 动画与性能优化 5. 现有库和框架 6. Vue 组件和状态管理 实践项目建议 案例1 案例2雪花 已经熟悉了 Vue、TypeScript 和 JavaScript&#xff0c;下面是一些你可以学习的内容&#xff0c;以帮助你实现粒子效果的界面&#…
阅读更多...
享界S9+问界M9，华为智选车的高端局

享界S9+问界M9，华为智选车的高端局

作者 |老缅 编辑 |德新 8月6日&#xff0c;鸿蒙智行在北京发布D级纯电旗舰轿车&#xff0c;也是北汽 - 华为智选车合作的第一款车型&#xff0c;享界S9。 享界S9搭载了包括华为乾崑ADS 3.0在内的多项首发技术&#xff0c;全系标配100kWh华为800V巨鲸电池。 而在价格上&#…
阅读更多...
记2024-08原生微信小程序开发

记2024-08原生微信小程序开发

继2024.08 最近需要开发一个微信小程序的一个功能模块&#xff0c;但是之前在学的时候都是好几年前的东东了&#xff0c;然后重新快速过了一遍b站大学的教程&#xff0c;这篇文章就是基于教程进行的一些总结&#xff0c;和自己开发过程当中使用到的一些点和一些技巧什么的吧。 …
阅读更多...
计算机网络408考研 2019

计算机网络408考研 2019

计算机网络408考研2019年真题解析_哔哩哔哩_bilibili 2019 1 1 1 1
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023