(C语言版)力扣(LeetCode)+牛客网(nowcoder)二叉树基础oj练习

news/2024/12/4 18:12:21/

在这里插入图片描述

二叉树基础oj练习

  • 965. 单值二叉树
    • 题目
    • 解法
  • 100. 相同的树
    • 题目
    • 解法
  • 101. 对称二叉树
    • 题目
    • 解法
  • 144. 二叉树的前序遍历
    • 题目
    • 解法
  • 94. 二叉树的中序遍历
    • 题目
    • 解法
  • 145. 二叉树的后序遍历
    • 题目
    • 解法
  • 572. 另一棵树的子树
    • 题目
    • 解法
  • KY11 二叉树遍历
    • 题目
    • 解法
  • 结语

965. 单值二叉树

题目

如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时,才返回 true;否则返回 false。

题目链接:单值二叉树

解法

代码如下:

bool isUnivalTree(struct TreeNode* root){if(!root)return true;if(root->left){if(root->val!=root->left->val||!isUnivalTree(root->left))return false;}if(root->right){if(root->val!=root->right->val||!isUnivalTree(root->right))return false;}return true;
}

首先判定二叉树是否为空,如果为空,直接返回true即可
再判定左右子树是否等值,不等返回false
嵌套递归下一层左右子树
遍历完都没进入条件语句,说明都相等,返回true

100. 相同的树

题目

给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

题目链接:相同的树

解法

代码如下:

bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(p==NULL&&q==NULL)return true;else if(p==NULL||q==NULL)return false;else if(p->val!=q->val)return false;else return(isSameTree(p->left,q->left)&&isSameTree(p->right,q->right));}

首先判定两树是否均为空,如果都为空,则返回true
有一个不为空则返回false
都不为空再比较值,不等则返回false
再向下递归遍历左右子树即可。

101. 对称二叉树

题目

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

题目链接:对称二叉树

解法

代码如下:

bool ret(struct TreeNode* p,struct TreeNode* q)
{if(!p&&!q)return true;else if(!p||!q)return false;else if(p->val!=q->val)return false;elsereturn ret(p->left,q->right)&&ret(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root){return ret(root,root);
}

这里还是使用递归的写法,由于这个算法需要两个参数实现,所以我们再写一个ret函数来实现,最后返回ret函数返回值即可

和上一题类似,如果树为空,则返回true,后面递归遍历时,是左右对称点比较
第二个条件也是为了后期递归时判断左右对称点是否一个为空,则返回false
第三个条件同理,判断值是否不等,不等则返回false
最后递归左右对称点,遍历整个二叉树。

144. 二叉树的前序遍历

题目

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

题目链接:二叉树的前序遍历

解法

代码如下:

void _preorder(struct TreeNode*root,int* ret,int* returnSize)
{if(root==NULL)return;ret[(*returnSize)++]=root->val;_preorder(root->left,ret,returnSize);_preorder(root->right,ret,returnSize);
} 
int* preorderTraversal(struct TreeNode* root, int* returnSize){int* ret=malloc(sizeof(int)*200);*returnSize=0;_preorder(root,ret,returnSize);return ret;
}

首先我们开辟一个数组空间,题目要求是[0,100],我这里是直接给了200,将returnSize初始化为0
再调用子函数,子函数首先判定结点为空直接不返回值
下面的三个就是关键了
前序遍历是按照二叉树根左右的顺序,所以
先将根节点的值放入数组,在递归遍历左子树,再递归遍历右子树
最后返回数组,结果即为二叉树的前序遍历。

94. 二叉树的中序遍历

题目

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

题目链接:二叉树的中序遍历

解法

代码如下:

void _inorder(struct TreeNode*root,int* ret,int* returnSize)
{if(root==NULL)return;_inorder(root->left,ret,returnSize);ret[(*returnSize)++]=root->val;_inorder(root->right,ret,returnSize);
} 
int* inorderTraversal(struct TreeNode* root, int* returnSize){int* ret=malloc(sizeof(int)*200);*returnSize=0;_inorder(root,ret,returnSize);return ret;
}

和上面的题目思路是一样的,只不过中序遍历顺序为左根右
所以我们将子函数稍微调整,先遍历左子树,再记录根节点,最后遍历右子树

145. 二叉树的后序遍历

题目

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。

题目链接:二叉树的后序遍历

解法

代码如下:

void _posorder(struct TreeNode*root,int* ret,int* returnSize)
{if(root==NULL)return;_posorder(root->left,ret,returnSize);_posorder(root->right,ret,returnSize);ret[(*returnSize)++]=root->val;} 
int* postorderTraversal(struct TreeNode* root, int* returnSize){int* ret=malloc(sizeof(int)*200);*returnSize=0;_posorder(root,ret,returnSize);return ret;
}

和上面的题目思路还是一样的,只不过后序遍历顺序为左右根
所以我们将子函数稍微调整,先遍历左子树,再遍历右子树,最后记录根节点

572. 另一棵树的子树

题目

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

题目链接:另一棵树的子树

解法

代码如下:

bool check(struct TreeNode* o, struct TreeNode* t)
{if (!o && !t) return true;if ((o && !t) || (!o && t) || (o->val != t->val)) return false;return check(o->left, t->left) && check(o->right, t->right);
}bool isSubtree(struct TreeNode* o, struct TreeNode* t)
{if (!o) return false;return check(o, t) || isSubtree(o->left, t) || isSubtree(o->right, t);
}

首先我们判定如果树为空直接返回false
再看下面的返回第一个条件
主树和子树如果都为空则返回true,只有一个为空或则值不相等则返回false
再比较主树的左子树和子树的左子树以及主树的右子树和子树的右子树
遍历完如果相同则为true,如果不同则向左子树再与子树比较,左子树不同再与右子树比较
都不同最后就返回false

KY11 二叉树遍历

题目

编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。

题目链接:二叉树遍历

解法

代码如下:

#include <stdio.h>
typedef struct TreeNode
{int* val;struct TreeNode* left;struct TreeNode* right;
}TreeNode;
TreeNode* creatTree(char* s,int* count)
{if(s[*count]=='#'||s[*count]=='\0')return NULL;TreeNode* newtree = malloc(sizeof(TreeNode));newtree->val=s[(*count)++];newtree->left=creatTree(s,count);(*count)++;newtree->right=creatTree(s,count);return newtree;
}
void inorder(TreeNode* root)
{if(root==NULL)return;inorder(root->left);printf("%c ",root->val);inorder(root->right);}
int main() {char s[200];scanf("%s",&s);int count=0;TreeNode* root=creatTree(s,&count);inorder(root);return 0;
}

首先是二叉树结构体的建立
包含值val和左右子树节点
然后是建二叉树,分别有输入值的字符串数组和初始化下标0两个参数
如果该元素为#或者\0则直接返回空即可
上述条件语句不执行则创建节点,根据二叉树前序遍历的顺序,先输入根的值,再遍历左子树,最后遍历右子树
然后是中序输出函数,节点为空,直接返回,
不执行上述条件语句,则按中序输出顺序,先遍历左子树节点,再输出根节点,最后遍历右子树节点
再看主函数
根据题意不超过100个字符,这里我直接给了200空间
然后就是输入字符串,初始化count为0,为了记录下标
最后调用建树和中序输出两个函数即可

结语

这里的解法代码部分来自力扣官方和作者自己的解法,作者只是进行了详细的剖析和部分改动方便大家理解和提升自己,学会多角度观察问题,解决问题。

有兴趣的小伙伴可以关注作者,如果觉得内容不错,请给个一键三连吧,蟹蟹你哟!!!
制作不易,如有不正之处敬请指出
感谢大家的来访,UU们的观看是我坚持下去的动力
在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!
在这里插入图片描述


http://www.ppmy.cn/news/73339.html

相关文章

springboot+java超市收银管理系统idea

考虑到实际生活中在超市 POS 收银管理方面的需要以及对该系统认真的分析&#xff0c;将系统权限按管理员和员工这两类涉及用户划分。 Spring Boot 是 Spring 家族中的一个全新的框架&#xff0c;它用来简化Spring应用程序的创建和开发过程。也可以说 Spring Boot 能简化我们之…

UML类图画法及其关系

UML类图画法及其关系 本文主要是介绍 UML类图画法及其关系&#xff0c;方便今后温习&#xff01;&#xff01;&#xff01; 一、类之间的关系汇总 泛化&#xff08;Generalization&#xff09;实现&#xff08;Realization&#xff09;关联&#xff08;Association&#xff…

Linux 学习笔记(七):时间片

一、时间片概念 时间片&#xff08;timeslice&#xff09;又称为 “量子”&#xff08;quantum&#xff09;或 “处理器片”&#xff08;processor slice&#xff09;&#xff0c;是分时操作系统分配给每个正在运行的进程微观上的一段 CPU 时间&#xff08;在抢占内核中是&…

将有序数组转换为二叉树

md这个破CSDN模板怎么没了&#xff0c;编辑器也死难用&#xff0c;气死 1、题目 给你一个整数数组 nums &#xff0c;其中元素已经按 升序 排列&#xff0c;请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不…

异地研发团队都使用哪些研发协同工具?盘点7类最主流的研发管理协同软件

产品研发场景下好用的协同办公软件有哪些&#xff1f;分享7类研发过程中主流的协同办公软件&#xff0c;比如项目管理协作与问题跟踪工具PingCode、代码托管与版本控制平台github、持续集成与持续部署&#xff08;CI/CD&#xff09;工具jinkens、文档协作与知识管理工具conflue…

Node开发Web后台服务

简介 Node.js 是一个基于Google Chrome V8 引擎的 JavaScript 运行环境。Node.js 使用了一个事件驱动、非阻塞式 I/O 的模型&#xff0c;使其轻量又高效。Node.js 的包管理器 npm&#xff0c;是全球最大的开源库生态系统。 能方便地搭建响应速度快、易于扩展的网络应用&#…

支付宝沙箱支付(java电脑版)

目录 下载支付demo配置环境AlipayConfig 下载支付demo 网址&#xff1a;https://open.alipay.com/ 下载并打开项目发现无法运行&#xff1a; 手动转化项目&#xff1a; 等待下载整理一下maven pom 通过tomat部署运行测试。 导入阿里支付的pom依赖 <dependency> &l…

《计算机网络—自顶向下方法》 Wireshark实验(十):NAT 协议分析

NAT&#xff08;Network Address Translation&#xff09;网络地址转换&#xff0c;即在私有地址和全局地址之间转换的协议。私有地址是不能用在 Internet 上(路由器将丢弃寻址这种地址的包)的内部地址。这些地址是不能够在公网上面用的&#xff0c;只能用在局域网的内部。私有…