力扣---二叉树OJ题(多种题型二叉树)

news/2024/5/19 0:28:19 标签: leetcode, 算法, 数据结构, c语言, 流程图

文章目录

  • 前言
  • 🌟一、剑指 Offer 55 - I. 二叉树的深度
    • 🌏1.1 链接：
    • 🌏1.2 代码一：
    • 🌏1.3 代码二：
    • 🌏1.4 流程图：
  • 🌟二、100. 相同的树
    • 🌏2.1 链接：
    • 🌏2.2 思路：
    • 🌏2.3 代码：
    • 🌏2.4 流程图：
  • 🌟三、965. 单值二叉树
    • 🌏3.1 链接：
    • 🌏3.2 思路：
    • 🌏3.3 代码：
    • 🌏3.4 流程图：
  • 🌟四、101. 对称二叉树
    • 🌏4.1 链接：
    • 🌏4.2 思路：
    • 🌏4.3 代码：
    • 🌏4.4 流程图：
  • 🌟五、144. 二叉树的前序遍历
    • 🌏5.1 链接：
    • 🌏5.2 代码(错误代码)：
    • 🌏5.3 流程图：
    • 🌏5.4 两种解决方法：
      • 5.4.1💫第一种：给i传地址
          • 📒代码：
      • 5.4.2💫第而种：全局变量
          • 📒代码：
  • 😽总结

前言

👧个人主页：@小沈熬夜秃头中୧⍤⃝❅
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：力扣—LeetCode刷题
🔑本章内容：力扣—二叉树OJ题
送给各位💌：活着就意味着要必须做点什么 请好好努力
欢迎 评论📝 +点赞👍 +收藏😽 +关注💞哦~

提示：以下是本篇文章正文内容，下面案例可供参考

🌟一、剑指 Offer 55 - I. 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。

请添加图片描述

🌏1.1 链接：

剑指 Offer 55 - I. 二叉树的深度

🌏1.2 代码一：

int maxDepth(struct TreeNode* root)
{
    if(root==NULL)
    return 0;
    int leftTree=maxDepth(root->left);
    int rightTree=maxDepth(root->right);
    return leftTree>rightTree?leftTree+1:rightTree+1;
}

🌏1.3 代码二：

这种代码是正确的但是在力扣上是不能通过的时间太长具体分析可以看【数据结构】—几分钟简单几步学会手撕链式二叉树(中)中求二叉树高度部分

int maxDepth(struct TreeNode* root)
{
	if (root == NULL)
		return 0;
	return maxDepth(root->left) > maxDepth(root->right) ?
		maxDepth(root->left) + 1 : maxDepth(root->right) + 1;
}

🌏1.4 流程图：

在这里插入图片描述

🌟二、100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

请添加图片描述

🌏2.1 链接：

100. 相同的树

🌏2.2 思路：

采用前序,先比较 根 然后 左子树 右子树，而结束条件就是为空树或者不相等

🌏2.3 代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if(p==NULL&&q==NULL)//两者都为空树则表示相同
    return true;
    if(p==NULL||q==NULL)//有一个不为空则不同
    return false;
    if(p->val!=q->val)//数值不同则不同
    return false;
    return isSameTree(p->left, q->left)&&isSameTree(p->right, q->right);//采用逻辑与当左树不相同时，就没必要比较右树
}

🌏2.4 流程图：

在这里插入图片描述

🌟三、965. 单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。

请添加图片描述

🌏3.1 链接：

965. 单值二叉树

🌏3.2 思路：

采用传递性：ab bc <> ac,然后通过对比根节点和左子树，左子树，右子树来判断值是否相同

🌏3.3 代码：

bool isUnivalTree(struct TreeNode* root)
{
    if(root==NULL)
    return true;
    if(root->left!=NULL&&root->left->val!=root->val)
    //左子树不为空且左子树的值和根值不同
    return false;
    if(root->right!=NULL&&root->right->val!=root->val)
    //右子树不为空且右子树的值和根值不同
    return false;
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

🌏3.4 流程图：

在这里插入图片描述

🌟四、101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

请添加图片描述

🌏4.1 链接：

101. 对称二叉树

🌏4.2 思路：

因为是轴对称，所以要比较左子树的值和右子树的值相同。

🌏4.3 代码：

bool _isSymmetric(struct TreeNode* leftRoot,struct TreeNode* rightRoot)
{
    if(leftRoot==NULL&&rightRoot==NULL)
    return true;
    if(leftRoot==NULL||rightRoot==NULL)
    return false;
    if(leftRoot->val!=rightRoot->val)
    return false;
    return _isSymmetric(leftRoot->left,rightRoot->right)
    &&_isSymmetric(leftRoot->right,rightRoot->left);
}
bool isSymmetric(struct TreeNode* root)
//这个函数是题给出的所以不能修改但不符合所以使用返回值
{
//因为题目给出根不为空所以只需要比较左右子树就可以了
    return _isSymmetric(root->left,root->right);
}

🌏4.4 流程图：

请添加图片描述

🌟五、144. 二叉树的前序遍历

🌏5.1 链接：

144. 二叉树的前序遍历

🌏5.2 代码(错误代码)：

下面这种写法是不能通过的，因为每次调用i++,都是各是各的造成了干扰具体可以看流程图

int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
void _preorderTraversal(struct TreeNode* root, int* a,int i)
{
    if(root==NULL)
    return;
    a[i++]=root->val;
    _preorderTraversal(root->left,a,i);
    _preorderTraversal(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize=TreeSize(root);
    int* a=(int*)malloc(sizeof(int)*(*returnSize));
    int i=0;
    _preorderTraversal(root,a,i);
    return a;
}

🌏5.3 流程图：

在这里插入图片描述

🌏5.4 两种解决方法：

5.4.1💫第一种：给i传地址

📒代码：
int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
void _preorderTraversal(struct TreeNode* root, int* a,int* pi)
{
    if(root==NULL)
    return;
    a[(*pi)++]=root->val;
    _preorderTraversal(root->left,a,pi);
    _preorderTraversal(root->right,a,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize=TreeSize(root);
    int* a=(int*)malloc(sizeof(int)*(*returnSize));
    int i=0;
    _preorderTraversal(root,a,&i);
    return a;
}

5.4.2💫第而种：全局变量

📒代码：

一点注意：要在一次调用后置零，不然下次调用时就会出现i在上一次的基础值上接着走而数组就不是从0开始的

int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
int i=0;
void _preorderTraversal(struct TreeNode* root, int* a)
{
    if(root==NULL)
    return;
    a[i++]=root->val;
    _preorderTraversal(root->left,a);
    _preorderTraversal(root->right,a);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize=TreeSize(root);
    int* a=(int*)malloc(sizeof(int)*(*returnSize));
    i=0;//注意这里
    _preorderTraversal(root,a);
    return a;
}

😽总结

请添加图片描述
😽Ending,今天的链式二叉树的内容就到此结束啦~，如果后续想了解更多，就请关注我吧，一键三连哦 ~


http://www.niftyadmin.cn/n/377496.html

相关文章

Linux :: 【基础指令篇 :: 文件及目录操作：(6)】:: rmidr / rm：删除空目录、删除非空目录及删除文件指令

Linux :: 【基础指令篇 :: 文件及目录操作：(6)】:: rmidr / rm：删除空目录、删除非空目录及删除文件指令

前言&#xff1a;本篇是 Linux 基本操作篇章的内容&#xff01; 笔者使用的环境是基于腾讯云服务器&#xff1a;CentOS 7.6 64bit。 学习集&#xff1a; C 入门到入土&#xff01;&#xff01;&#xff01;学习合集Linux 从命令到网络再到内核&#xff01;学习合集 目录索引&am…
阅读更多...
JeecgBoot企业级开发中实现自定义导出EXCEL的前端表格字段功能

JeecgBoot企业级开发中实现自定义导出EXCEL的前端表格字段功能

文章目录 如何在后端实现导出前端列表字段到Excel功能需求前端的实现1. 提供一个导出的点击函数2.引入组件中的userMethod3.tableProps中导出中添加对应的查询参数4. 编写导出函数 后端逻辑的实现1.Controller层2.创建Modal类3.Sevice层 检验成果总结 如何在后端实现导出前端列…
阅读更多...
【实用篇】SpringCloud02

【实用篇】SpringCloud02

文章目录 SpringCloud020.学习目标1.Nacos配置管理1.1.统一配置管理1.1.1.在nacos中添加配置文件1.1.2.从微服务拉取配置 1.2.配置热更新1.2.1.方式一1.2.2.方式二 1.3.配置共享1&#xff09;添加一个环境共享配置2&#xff09;在user-service中读取共享配置3&#xff09;运行两…
阅读更多...
生鲜农产品冷链物流配送路径优化模型构建及算法实现

生鲜农产品冷链物流配送路径优化模型构建及算法实现

摘要&#xff1a;本案例讲述的案例为生鲜农产品冷链物流配送路径优化&#xff0c;涉及的目标函数成本包括碳排放成本、固定成本、运输成本、货损变质成本、时间惩罚成本。 目标种类&#xff1a;单目标模型。 求解方法&#xff1a;基础版蚁群算法改进版蚁群算法。 整体对标层…
阅读更多...
图解系列 图解Spring Boot 最大连接数及最大并发数

图解系列 图解Spring Boot 最大连接数及最大并发数

文章目录 概序架构图TCP的3次握手4次挥手时序图核心参数AcceptCountMaxConnectionsMinSpareThread/MaxThreadMaxKeepAliveRequestsConnectionTimeoutKeepAliveTimeout 内部线程AcceptorPollerTomcatThreadPoolExecutor 测试参考 每个Spring Boot版本和内置容器不同&#xff0c;…
阅读更多...
java学习 spring mybatis maven juc并发 缓存

java学习 spring mybatis maven juc并发 缓存

Spring系列第11篇&#xff1a;bean中的autowire-candidate又是干什么的&#xff1f;_路人甲Java的博客-CSDN博客 Spring系列 Spring系列第1篇&#xff1a;为何要学spring&#xff1f; Spring系列第2篇&#xff1a;控制反转&#xff08;IoC&#xff09;与依赖注入&#xff08;DI…
阅读更多...
Android 架构模式

Android 架构模式

1.三个基本架构 ①MVC&#xff08;Model-View-Controller&#xff09; Model&#xff1a;代表数据模型&#xff0c;管理数据状态。 View&#xff1a;视图&#xff0c;即呈现给用户的UI&#xff0c;包括布局文件及Activity。 Controller&#xff1a;控制者&#xff0c;负责处…
阅读更多...
23种设计模式之策略模式（Strategy Pattern）

23种设计模式之策略模式（Strategy Pattern）

前言&#xff1a;大家好&#xff0c;我是小威&#xff0c;24届毕业生&#xff0c;在一家满意的公司实习。本篇文章将23种设计模式中的策略模式&#xff0c;此篇文章为一天学习一个设计模式系列文章&#xff0c;后面会分享其他模式知识。 如果文章有什么需要改进的地方还请大佬不…
阅读更多...
最新文章

Copyright @ 2022~2023