前言
笔者终于期末考完回来啦!力扣系列终于可以重新开始更新了惹~
本来是打算把二叉树也作为每日一题每天更新多水几篇文章,咳咳,多写几天的,毕竟一口吃不成一个胖子嘛,凡是都要慢慢来是吧。但是这个坑留的越久,以后内容多了这个坑就填不起来了,所以今天就统一暴力一点,把这个坑填上了
以下的oj题都是二叉树的基本题目,基本都涉及了递归和分治的思想
目录
- 单值二叉树
- 二叉树的最大深度
- 翻转二叉树
- 二叉树的前序遍历
- 检查两棵树是否相同
- 平衡二叉树
- 另一颗树的子树
- 对称二叉树
单值二叉树
原题链接
题目描述
如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时,才返回 true;否则返回 false。
例如:
上图就是一颗单值二叉树
思路求解
我们在这篇文章中可以继续采用分而治之的思想
我们可以检查,只要树的左子树和右子树和根的值相同就行了
检查左子树和右子树时,同样,只需检查左右子树的左右子树是否与它们相同就行了
动图:
代码实现
bool isUnivalTree(struct TreeNode* root){
if(!root)
return true;//空树也算单值二叉树,还有就是可以一直遍历到最后一层返回true
if(root->left&&root->val!=root->left->val)
return false;
if(root->right&&root->val!=root->right->val)
return false;//不等于的直接返回false
return isUnivalTree(root->left)&&isUnivalTree(root->right);
}
二叉树的最大深度
原题链接
题目描述
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
例如:
有三层,所以返回3
思路求解
我们要做这道题,只需要算出左右子树中哪个深度较大,最后在加上根结点,也就是较大深度+1,左右子树使用同样的算法
动图:
代码实现:
int maxDepth(struct TreeNode* root){
if(!root)
return 0;
if(root->left==root->right)
return 1;
int leftDepth=maxDepth(root->left);
int rightDepth=maxDepth(root->right);//用中间变量保存,防止递归次数过多
return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
}
翻转二叉树
原题链接
题目描述
思路求解
根据题意,我们可以观察到所谓的翻转就是将左子树和右子树的结点相互交换,同样,左子树和右子树的子树也同样需要交换。
这里需要判断几种情况:
为叶子结点时,也就是左右子树均为空,不需要交换,直接返回结点即可
空树直接返回空
其它情况直接交换即可
难度不大,直接按着思路写代码即可
struct TreeNode* invertTree(struct TreeNode* root){
struct TreeNode* ret=root;
if(!root)
return NULL;
if(root->left==root->right)
return root;
struct TreeNode* tmp=root->left;
root->left=root->right;
root->right=tmp;//这里是交换左右
invertTree(root->left);//递归下去交换即可
invertTree(root->right);
return root;
}
二叉树的前序遍历
原题链接
题目描述
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
例如:
返回:1,2,3
注意,本题需要数组存储遍历出的值
思路求解
既然需要数组存储数据,所以我们必须要知道我们要开辟多少空间
所以我们第一步就需要计算出这个二叉树有多大,(在二叉树基础中我已经介绍了算法,所以这里不再阐述)
但难点就是遍历树的时候(递归的时候)数组下标中i的控制
因为函数出了作用域后局部变量的值会被销毁,但递归需要调用很多次,所以需要保存i此时的值,就需要用到指针来控制了
知道了这个,这题就能轻松求出来
void _PrevOrder(struct TreeNode* root,int* arr,int* i)//遍历子函数
{
if(!root)
return;
arr[(*i)++]=root->val;
_PrevOrder(root->left,arr,i);
_PrevOrder(root->right,arr,i);
}
int BinTreeSize(struct TreeNode* root)//求树的大小
{
if(!root)
return 0;
return BinTreeSize(root->left)+BinTreeSize(root->right)+1;
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize=BinTreeSize(root);
int* arr=(int*)malloc(sizeof(int)*(*returnSize));
int i=0;
_PrevOrder(root,arr,&i);
return arr;
}
检查两棵树是否相同
原题链接
题目描述
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
例如:
这两棵树相同
这两棵树不同
思路求解
这题同样使用上面用到的分治思想,有以下几种情况
p和q树都为空,两棵树肯定相同
其中有一个都不为空都不相同
其实有一个结点不相同都不是相同的
然后顺序往下找即可
代码实现
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(!p&&!q)
return true;
if(!p&&q)
return false;
if(p&&!q)
return false;
if(p->val!=q->val)
return false;
return isSameTree(p->left,q->left)&&
isSameTree(p->right,q->right);
}
平衡二叉树
原题链接
题目描述
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
例如:
是平衡二叉树
思路求解
首先,这道题涉及到求深度,所以需要用到我们在二叉树基础中用过的判断深度的函数
需要深度之差不超过1,只需要用到abs函数来判断
其中,只要深度之差超过2,立刻返回false
直到将全树递归完为止
代码实现
int maxDepth(struct TreeNode* root){
if(!root)
return 0;
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return left>right ? left+1 :right+1;
}//判断深度的函数
bool isBalanced(struct TreeNode* root){
if(!root)
return true;
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return abs(left-right)<2
&&isBalanced(root->left)
&&isBalanced(root->right);//绝对值小于2,以及左右子树同时为平衡二叉树,才为真,否则为假
}
另一颗树的子树
原题链接
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
例如:
思路求解
我们在这里,如果需要判断是否有子树,首先需要一个判断树是否相同的函数
在递归中也分几种情况
空树肯定没有子树,返回false
找到相同的子树后,返回true
本题是找子树,只需要左右只有一个子树就行了,也就是用或运算符
代码实现
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(!p&&!q)
return true;
if(!p&&q)
return false;
if(p&&!q)
return false;
if(p->val!=q->val)
return false;
return isSameTree(p->left,q->left)&&
isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(!root)
return false;//空树肯定没有子树,返回false
if(isSameTree(root,subRoot))
return true;
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}
对称二叉树
原题链接
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
思路求解
这里与判断二叉树相同相似,只需要将左右子树当作两颗不同的树来比较即可
但是这里的比较跟判断相同还是有点区别的
根据镜像对称的特点,这里需要左子树与右子树对比,右子树与左子树对比
代码实现
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(!p&&!q)
return true;
if(!p&&q)
return false;
if(p&&!q)
return false;
if(p->val!=q->val)
return false;
return isSameTree(p->left,q->right)&&
isSameTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root){
if(!root)
return true;
return isSameTree(root->left,root->right);
}