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

【LeetCode刷题指南】--二叉树的前序遍历,二叉树的中序遍历

🔥个人主页:@草莓熊Lotso

🎬作者简介:C++研发方向学习者

📖个人专栏: 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言:生活是默默的坚持,毅力是永久的享受。 

前言:在之前的C语言刷题集中我们刷了很多IO类型的基础编程题,但是随着数据结构往后的学习以及企业面试的要求,我们还需要对接口型的题目进行练习,博主在这里准备了新的《LeetCode刷题指南》专栏给大家分享一些我自己在力扣上面写过的题目,提供一些我的解题思路。个人实力有限,欢迎大家补充和指正。


目录

一.二叉树的前序遍历

解题过程: 

代码实现: 

 二.二叉树的中序遍历

解题过程:

代码实现: 


一.二叉树的前序遍历

题目链接:144. 二叉树的前序遍历 - 力扣(LeetCode)

题目描述: 

 题目示例:

思路: 前序遍历,动态开辟数组

解题过程: 

1. returnsize表示要返回的数组的大小,我们这里需要动态开辟数组所申请的空间也是 returnsize*sizeof(int), 这个我们需要实现一个TreeSize函数来解决(结点个数=根节点+左子树节点个数+右子树节点个数)

2.注意我们代码里面传的i需要传地址,这里其实就是把我们之前实现的前序遍历的函数参数改了一下,然后在函数里的打印换成了用数组存储

3.最后都结束了之后,直接返回ans就可以了

复杂度:

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

代码实现: 

/*** 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().*/
typedef struct TreeNode TreeNode;
void PrevOrder(TreeNode*root,int*ans,int*pi)
{if(root==NULL){return;}ans[(*pi)++]=root->val;PrevOrder(root->left,ans,pi);PrevOrder(root->right,ans,pi);
}
int TreeSize(TreeNode*root)
{if(root==NULL){return 0;}return 1+TreeSize(root->left)+TreeSize(root->right);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int*ans=(int*)malloc(sizeof(int)*(*returnSize));int i=0;PrevOrder(root,ans,&i);return ans;
}

 二.二叉树的中序遍历

题目链接:94. 二叉树的中序遍历 - 力扣(LeetCode)

题目描述: 

题目示例: 

思路: 中序遍历,动态开辟数组

解题过程:

1. returnsize表示要返回的数组的大小,我们这里需要动态开辟数组所申请的空间也是 returnsize*sizeof(int), 这个我们需要实现一个TreeSize函数来解决(结点个数=根节点+左子树节点个数+右子树节点个数)

2.注意我们代码里面传的i需要传地址,这里其实就是把我们之前实现的中序遍历的函数参数改了一下,然后在函数里的打印换成了用数组存储

3.最后都结束了之后,直接返回ans就可以了

复杂度:

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

代码实现: 

/*** 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().*/
typedef struct TreeNode TreeNode;
void InOrder(TreeNode*root,int*ans,int*pi)
{if(root==NULL){return;}InOrder(root->left,ans,pi);ans[(*pi)++]=root->val;InOrder(root->right,ans,pi);
}int TreeSize(TreeNode*root)
{if(root==NULL){return 0;}return 1+TreeSize(root->left)+TreeSize(root->right);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int*ans=(int*)malloc(sizeof(int)*(*returnSize));int i=0;InOrder(root,ans,&i);return ans;
}

往期回顾:

【LeetCode刷题指南】--随机链表的复制

【LeetCode刷题指南】--有效的括号

【LeetCode刷题指南】--队列实现栈,栈实现队列

【LeetCode刷题指南】--单值二叉树,相同的树

结语:本篇文章就到此结束了,《LetetCode刷题指南》中的题目比起之间的C语言刷题集中的题目,肯定会更加复杂一些。而且题目形式也不一样,大家需要注意一下。如果文章对你有帮助的话,欢迎评论,点赞,收藏加关注,感谢大家的支持。

http://www.lryc.cn/news/607802.html

相关文章:

  • 2025熵密杯 -- 初始谜题 -- Reproducibility
  • 进阶向:自动化天气查询工具(API调用)
  • stm32是如何实现电源控制的?
  • 【7.5 Unity AssetPostprocessor】
  • 2-5 Dify案例实践—利用RAG技术构建企业私有知识库
  • 【最新区块链论文录用资讯】CCF A--WWW 2025 23篇
  • 第三章 用户和权限
  • 【C++】第二十一节—一文详解 | 红黑树实现(规则+效率+结构+插入+查找+验证)
  • 【RK3568 RTC 驱动开发详解】
  • 网安-中间件(updating..)
  • jenkins从入门到精通-P1—九五小庞
  • 【机器学习】非线性分类算法详解(下):决策树(最佳分裂特征选择的艺术)与支持向量机(最大间隔和核技巧)
  • Docker 的网络模式
  • OTC焊接机器人节能技巧
  • Python 第一阶段测试题 答案及解析
  • 机器学习【五】decision_making tree
  • 高性能MCP服务器架构设计:并发、缓存与监控
  • 淘宝小程序的坑
  • Clickhouse#表记录转换为insert语句
  • 【机器学习】“回归“算法模型的三个评估指标:MAE(衡量预测准确性)、MSE(放大大误差)、R²(说明模型解释能力)
  • Human Brain Mapping:静息态功能磁共振成像的回归动态因果建模
  • C语言(长期更新)第7讲:VS实用调试技巧
  • ADB 底层原理
  • Android 运行 deno 的新方法 (3): Termux 胖喵安初
  • 【Leetcode hot 100】49.字母异位词分组
  • [mssql] 分析SQL Server中执行效率较低的SQL语句
  • imx6ull-驱动开发篇6——Linux 设备树语法
  • 快速了解决策树
  • 四、Portainer图形化管理实战与Docker镜像原理
  • 音视频学习(四十五):声音的产生