发布于2021-06-07 20:15 阅读(1013) 评论(0) 点赞(18) 收藏(4)
前几天的文章中我写到了二叉树的操作实现,但是一直都没有机会来自己刷刷OJ,今天他来了,准备了好几道题来供大家参考,加固一下我的知识顺便来巩固一下大家的理解,是不是一举两得呢?时间有限,我就不画图展示了,你们这么聪明一定可以看懂的对吧,大概的实现思路我会留在代码处,必要的朋友可以联系我一起讨论啊!
往下看,干货都在下面~
如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时,才返回 true;否则返回 false。
提示:
给定树的节点数范围是 [1, 100]。
每个节点的值都是整数,范围为 [0, 99] 。
//用递归来实现
//val值与root->val值相等即为真
bool _isUnivalTree(struct TreeNode* root,int val){
if(root == NULL)
return true;
if(val != root->val)
return false;
return _isUnivalTree(root->left,val) &&
_isUnivalTree(root->right,val);
}
bool isUnivalTree(struct TreeNode* root){
return _isUnivalTree(root,root->val);
}
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点
int maxDepth(struct TreeNode* root){
//判空
if(root == NULL)
return 0;
//不为空,则高度即为左右子树较大者+1
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return left > right ? left+1 : right+1;
}
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
//两棵树都为空
if(p == NULL && q == NULL)
return true;
//有一棵树为空
if(p == NULL || q == NULL)
return false;
//都不为空,判断两棵树相同位置的节点值是否相等、左右孩子的节点是否相同
return p->val ==q->val &&
isSameTree(p->left,q->left) &&
isSameTree(p->right,q->right);
}
翻转一棵二叉树。
struct TreeNode* invertTree(struct TreeNode* root){
//判空
if(root == NULL)
return NULL;
//交换根节点的左右子节点
struct TreeNode* tmp = root->left;
root->left = root->right;
root->right = tmp;
//递归向下直到全部交换
invertTree(root->left);
invertTree(root->right);
return root;
}
给定一个二叉树,检查它是否是镜像对称的。
//这个问题可以这样实现
//可以把这颗树拷贝一份,然后递归比较根节点和左右子树,如果都相同则对称
bool _isSymmetric(struct TreeNode* root1,struct TreeNode* root2)
{
//都为空则对称
if(root1 == NULL && root2 ==NULL)
return true;
//有一个为空,不对称
if(root1 == NULL || root2 ==NULL)
return false;
//递归比较左子树和右子树,都满足则对称
return root1->val==root2->val &&
_isSymmetric(root1->right,root2->left) &&
_isSymmetric(root1->left,root2->right);
}
bool isSymmetric(struct TreeNode* root){
return _isSymmetric(root,root);
}
给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
bool equal(struct TreeNode* s,struct TreeNode* t)
{
//首先比较根节点,若根节点同时为空,则两树相等。
//若其中一个为空,另一个非空,则两树不等。
//若节点上的数值不等,则两树不等。
if(!s &&!t)
return true;
if(s == NULL || t == NULL)
return false;
if(s->val != t->val)
return false;
//节点上的数值相等,进而要向下比较它们的子树是否相等,使用递归,分别比较左右子树是否相等,注意:一定要都相等才可以。
return s->val == t->val &&
equal(s->left,t->left) &&
equal(s->right,t->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
//递归到最后,root都已经为空了,那么再无相等可言,return false;
if(!root)
return false;
//选择往那边走
return equal(root,subRoot)||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
//先求出该树的深度(层数)
int height(struct TreeNode* root)
{
if(root == NULL)
{
return 0;
}
int left = height(root->left);
int right = height(root->right);
return left > right ? left+1 : right+1;
}
//自顶向下,递归
bool isBalanced(struct TreeNode* root){
//空树是平衡二叉树
if(root == NULL)
{
return true;
}
//三个条件都满足即可
//其根节点的左右子树的高度差不超过1,然后递归往下走
return fabs(height(root->left) - height(root->right)) <=1 &&
isBalanced(root->left) &&isBalanced(root->right);
}
编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。
输入描述:
输入包括1行字符串,长度不超过100。
输出描述:
可能有多组测试数据,对于每组数据, 输出将输入字符串建立二叉树后中序遍历的序列,每个字符后面都有一个空格。 每个输出结果占一行。
#include<stdio.h>
#include<assert.h>
#include<malloc.h>
#include<string.h>
typedef struct TreeNode
{
char data;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;
//开辟内存
TreeNode* BuyTreeNode(char ch)
{
TreeNode* node=(TreeNode*) malloc(sizeof(TreeNode));
if(node == NULL)
{
return NULL;
}
node->data = ch;
node->left = node->right = NULL;
return node;
}
//创建树
TreeNode* TreeNodeCreate(char arr[],int size,int *index)
{
TreeNode* root = NULL;
if(*index < size && '#' != arr[*index])//index小于size并且arr[*index]不等于’#‘
{
root = BuyTreeNode(arr[*index]);//创建根节点
//数组往后走创建左子树
(*index)++;
root->left = TreeNodeCreate(arr, size, index);
//数组往后走创建右子树
(*index)++;
root->right = TreeNodeCreate(arr, size, index);
}
return root;
}
//中序遍历
void InorderTreeNode(TreeNode* root)
{
if(root == NULL)
return;
InorderTreeNode(root->left);
printf("%c ",root->data);
InorderTreeNode(root->right);
}
//销毁树
void DestroyTree(TreeNode** root)
{
if(*root)
{
DestroyTree(&(*root)->left);
DestroyTree(&(*root)->right);
free(*root);
(*root) = NULL;
}
}
int main()
{
char arr[100];
//多组输入
while(scanf("%s",arr) != EOF)
{
int index = 0;
TreeNode* root = TreeNodeCreate(arr,strlen(arr),&index);
InorderTreeNode(root);
printf("\n");
DestroyTree(&root);
}
return 0;
}
以上就是本篇文章的重点,今天就到此结束了哈,有不同的观点或者有不同思路的朋友欢迎大家赏光私我哈,本着相互进步的原则,希望大家能多多向我提意见,谢谢~~
作者:bbjbbh
链接:http://www.phpheidong.com/blog/article/89479/fe1ad3029c12dca791fe/
来源:php黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 php黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-4
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!