🌈个人主页：努力学编程’
⛅个人推荐：基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解
⚡学好数据结构，刷题刻不容缓：点击一起刷题
🌙心灵鸡汤：总有人要赢，为什么不能是我呢
hello 大家好啊，前两天给大家写了关于二叉树的一些知识点，上次也说过了，二叉树是非常重要的数据结构，必须熟悉二叉树的基本知识，并学会对二叉树的一些基本操作，博主下去把上次讲的二叉树的知识，做成了一个思维导图，今天带大家刷几道二叉树的题，如果那块知识有问题，可以顺着思维导图看看，也可以看看我的上一篇文章【java数据结构-二叉树(上)】.
二叉树相关的算法题
🚀检查两颗树是否相同
解题思路：我们知道二叉树的结构非常的简单，大体可以分为数值和数的结构构成，而且我们上次说过二叉树的核心就是递归所以，我们这里要两个树相同，可以这样想两棵树的根节点的值和结构一样，并且左子树和右子树的结构和值一样。
class Solution {
public boolean isSameTree(TreeNode p,TreeNode q){
//一个为空，另一个不为空必不相同
if(p==null&&q!=null||p!=null&&q==null){
return false;
}
//两棵树都是空的，则两棵树相同
if(p==null&&q==null){
return true;
}
//两棵树的节点的值不相同，就不相同
if(p.val!=q.val){
return false;
}
//保证左右子树的节点结构和值相同
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
另一颗树的子树
解题思路：如何判断这两棵树是否存在子树的关系呢，这里直接思考整个过程可能有点难度，我们可以从·特殊情况入手，比如两棵树如果一模一样的话，那么此时当然也满足子树的条件，此时就是我们上一道题的解题过程，如果不一样的话，由于两棵树都不为空，所以我们不必考虑为空的情况，接下来，我们就需要判断root中包含subRoot的情况了。
直接上代码：
class Solution {
public boolean isSubtree(TreeNode root,TreeNode subRoot){
if(root==null){
return false;
}
if(isSameTree(root, subRoot)){
return true;
}
if(isSubtree(root.left,subRoot)){
return true;
}
if(isSubtree(root.right,subRoot)){
return true;
}
return false;
}
public boolean isSameTree(TreeNode p,TreeNode q){
if(p==null&&q!=null||p!=null&&q==null){
return false;
}
if(p==null&&q==null){
return true;
}
if(p.val!=q.val){
return false;
}
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
翻转二叉树
解题思路：对于二叉树的翻转，我们可能比较陌生，但这个题其实是最简单的，思路也比较直接，翻转二叉树首次翻转头结点的左子树和右子树，然后翻转左子树节点的左右子树，和右子树的左右子树如此递归就完成了二叉树的翻转。
直接上代码：
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null){
return null;
}
TreeNode ret=root.left;
root.left=root.right;
root.right=ret;
invertTree(root.right);
invertTree(root.left);
return root;
}
}
判断一颗二叉树是否是平衡二叉树
解题思路：首先你得知道什么是平衡二叉树，即这棵树的所有节点对应的左子树和右子树的差值必须小于等于1，否则就不是平衡二叉树。一棵树如果是平衡二叉树，那它的头结点的左子树和右子树的长度之差必须小于等于1，同时对应的左子树和对应的右子树必须也是平衡二叉树，好了现在又引出了一个新的问题，如何获取子树的长度，仔细思考，我们还得编写一个求长度的方法，求一棵树的长度就是我们一直求左子树和右子树长度然后比较求出较长的树的长度，加上头结点即1就求出了长度
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
int leftH = maxDepth(root.left);
int rightH = maxDepth(root.right);
return Math.abs(leftH - rightH) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return leftHeight > rightHeight ?
leftHeight+1:rightHeight+1;
}
}
对称二叉树
同样我们先要理解对称二叉树的概念，对称二叉树，即以每棵树的头结点为对称点左右两边的树的结构和数值都是一致的，大家仔细品味这句话，基本上已经把对称二叉树的概念说的很明白了，同样的头结点对应的左右子树要对称，而此时的左右子树也要是对称二叉树，接着就一直递归下去，知道结束。
上代码
class Solution {
public boolean isSymmetric(TreeNode root){
if(root==null){
return true;
}
return isSymmetricChild(root.left,root.right);
}
public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
//检查结构是否相同
if(leftTree!=null&&rightTree==null||leftTree==null&&rightTree!=null){
return false;
}
//结构是否相同 两个都为空 两个都不为空
if(leftTree==null&&rightTree==null){
return true;
}
if(leftTree.val!=rightTree.val){
return false;
}
//此时两个节点都不为空，且值都一样，结构相同，
//接着判断左子树的右 和右子树的左 左子树的左和右子树的右 是否对称
return isSymmetricChild(leftTree.left,rightTree.right)
&&isSymmetricChild(leftTree.right,rightTree.left);
}
}
结语
今天就带大家学习这么多的东西了，关于二叉树，其实还有很多难度更大的题目，在此之前一定要把二叉树的基本知识了解清楚，理解二叉树中的递归过程，多多画图理解，最后一定要及时总结哦~~~，期待你的一键三连！！！
