大公司做网站的优势,产品网络推广方案,中小型企业网络部署,wordpress分类设置主题✨✨欢迎大家来到Celia的博客✨✨ #x1f389;#x1f389;创作不易#xff0c;请点赞关注#xff0c;多多支持哦#x1f389;#x1f389; 所属专栏#xff1a;OJ题 个人主页#xff1a;Celias blog~ 目录
编辑
单值二叉树
题目描述 OJ-单值二叉树
解题思路
… ✨✨欢迎大家来到Celia的博客✨✨ 创作不易请点赞关注多多支持哦 所属专栏OJ题 个人主页Celias blog~ 目录
编辑
单值二叉树
题目描述 OJ-单值二叉树
解题思路
代码实现
二叉树的最大深度
题目描述 OJ-二叉树的最大深度
解题思路
代码实现
检查两棵树是否相同
题目描述 OJ-相同的树
解题思路
代码实现
对称二叉树
题目描述 OJ-对称二叉树
解题思路
代码实现
另一颗树的子树
题目描述 OJ-另一颗树的子树
解题思路
代码实现
翻转二叉树
题目描述 OJ-翻转二叉树
解题思路
代码实现
平衡二叉树
题目描述 OJ-平衡二叉树
解题思路
代码实现 单值二叉树 题目描述 OJ-单值二叉树 如果二叉树每个节点都具有相同的值那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时才返回 true否则返回 false。 解题思路
本题的核心是判断左右子树的val的值是否和主干的val相等。
若节点为空则返回true。若不相等返回false。如果这两个条件都不满足则递归判断左右子树。
该题调用的函数参数只有一个二叉树节点指针。为了方便起见可以额外写一个子函数来进行递归子函数的参数为二叉树节点指针root和该节点的值val。 返回true的情况示例 绿色数字为执行顺序 返回false的情况示例 绿色数字执行顺序 代码实现
bool _isUnivalTree(struct TreeNode* root,int val)
{if(root NULL)return true;if(root-val ! val)return false;return _isUnivalTree(root-left,val) _isUnivalTree(root-right,val);
}
bool isUnivalTree(struct TreeNode* root)//系统调用的函数
{return _isUnivalTree(root,root-val);
}
二叉树的最大深度 题目描述 OJ-二叉树的最大深度 给定一个二叉树 root 返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 解题思路
本题的关键在于该树的深度为左右子树中最大的深度。
如果传入的节点为空则返回0。如果节点不为空则递归计算左右两个子树的深度并且定义两个整型变量记录下来。最后返回左右子树深度中值最大的一个。 递归遍历求深度示例 绿色数字执行顺序 代码实现
int maxDepth(struct TreeNode* root) {if(root NULL)return 0;int l maxDepth(root-left);int r maxDepth(root-right);return l r ? l 1 :r 1;
}
在这里要注意一定要用两个变量接收左右子树的深度不可以将递归函数写在三目运算符中
return maxDepth(root-left) maxDepth(root-right) ? maxDepth(root-left) 1 : rmaxDepth(root-right) 1;
上面的写法会导致过多的重复运算严重拖慢了运行时间。
检查两棵树是否相同 题目描述 OJ-相同的树 给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 解题思路
如果传入的节点都为空则返回true。如果只有其中一个为空另一个不为空则返回false。如果传入的节点都不为空但是这两颗树当前节点值不同返回false。递归遍历两个左右子树左子树和左子树比较右子树和右子树比较返回两个递归逻辑与的结果。 代码实现
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);
}
对称二叉树 题目描述 OJ-对称二叉树 给你一个二叉树的根节点 root 检查它是否轴对称。 解题思路
这道题和 OJ-相同的树 思路是一样的唯一需要改变的地方为相同的树是相同方向的树进行比较,而本题是不同方向的树进行比较。 代码实现
bool _isSymmetric(struct TreeNode* r1,struct TreeNode* r2)
{if(r1 NULL r2 NULL)return true;if(r1 NULL || r2 NULL)return false;if(r1-val ! r2-val)return false;return _isSymmetric(r1-right,r2-left) _isSymmetric(r1-left,r2-right);
}
bool isSymmetric(struct TreeNode* root)
{return _isSymmetric(root-left,root-right);
}
另一颗树的子树 题目描述 OJ-另一颗树的子树 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。 解题思路
本题提供的subRoot树一定为非空那么如果传入的root节点为空则一定不包含子树返回false。先判断subRoot树和root树的当前节点的值是否相同若相同检查以当前节点为根节点的树是否为subRoot树如果是返回true。以左右子树为根节点递归左右子树返回它们逻辑或的结果。左右只要含有子树就符合题意 代码实现
本题用到了 OJ-相同的树 的代码。
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);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{if(root NULL)return false;if(root-val subRoot-val isSameTree(root,subRoot))return true;return isSubtree(root-left,subRoot) || isSubtree(root-right,subRoot);}
翻转二叉树 题目描述 OJ-翻转二叉树 给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 解题思路
如果传入的节点为空返回NULL。如果传入的节点非空则交换左右子树节点的值。递归调用左右子树。返回根节点。 代码实现
struct TreeNode* invertTree(struct TreeNode* root)
{if(root NULL)return NULL;struct TreeNode* tmp root-right;root-right root-left;root-left tmp;invertTree(root-left);invertTree(root-right);return root;
}
平衡二叉树 题目描述 OJ-平衡二叉树 给定一个二叉树判断它是否是 平衡二叉树。平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。 解题思路
如果传入的节点为空返回true。定义两个变量记录当前节点的左右子树的深度并求出左右子树相差的绝对值。若绝对值大于1返回false。递归调用左右子树返回它们逻辑与的结果左右两边都必须平衡。 代码实现
本题用到了 OJ-二叉树的最大深度 的代码。
int TreeHeight(struct TreeNode* root)
{if(root NULL)return 0;int r TreeHeight(root-left);int r1 TreeHeight(root-right);return r1 r ? r1 1 : r 1;
}
bool isBalanced(struct TreeNode* root)
{if(root NULL)return true;int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-right);int size abs(leftHeight - rightHeight);//求绝对值if(size 1)return false;return isBalanced(root-left) isBalanced(root-right);
}
