您现在的位置是:首页 >技术交流 >(C语言版)力扣(LeetCode)+牛客网(nowcoder)二叉树基础oj练习网站首页技术交流
(C语言版)力扣(LeetCode)+牛客网(nowcoder)二叉树基础oj练习
二叉树基础oj练习
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;
else
return 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]=='