个人主页：欢迎大家光临——>沙漠下的胡杨

  各位大帅哥，大漂亮

 如果觉得文章对自己有帮助

 可以一键三连支持博主

 你的每一分关心都是我坚持的动力

 

 ☄： 本期重点：二叉树的习题

  希望大家每天都心情愉悦的学习工作。 

我们在经过之前的学习，我们对二叉树有一定的理解了，我们尝试着写下力扣的习题吧。

​​​​​​965. 单值二叉树

单值二叉树讲解：

单值二叉树，如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false

思路一：

我们可以使用前序遍历的思想。

1. 我们先创建一个bool值赋值为true。

2.前序遍历比较，如果值不相等，那么就把 bool 值改为 false，如果相等就比较左树，在比较右树。

3.如果是空树，或者bool值为false时，就返回。

4.我们每次使用bool值时都要手动置为true。

代码实现：

bool flag = true;//定义布尔值void PreOrderCompare(struct TreeNode *root,int val){    if(root == NULL || flag == false)//如果为空或者布尔值为false就返回    { return;    }    if(root->val != val)//如果结点值不一样，bool值改为false    { flag = false; return ;    }    PreOrderCompare(root->left,val);    PreOrderCompare(root->right,val);}bool isUnivalTree(struct TreeNode* root){    if(root == NULL)    { return true;    }    flag = true;//手动把布尔值置为true    PreOrderCompare(root,root->val);    return flag;}

思路二：

1.我们可以判断根的左子树和右子树在不为空的情况下，左右子树的值是否不相等？

2.然后在访问左子树右子树，递归进行。

bool isUnivalTree(struct TreeNode* root){    if(root == NULL)//如果为空返回true    { return true;    } //左子树不为空，并且左子树的值不等于根节点的值，返回false    if(root->left && root->val != root->left->val)    { return false;    }    //右子树不为空，并且右子树的值不等于根节点的值，返回false if(root->right && root->val != root->right->val)    { return false;    }    return isUnivalTree(root->left) && isUnivalTree(root->right);}

​​​​​​100. 相同的树

相同的树讲解：

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

思路：

我们可以把 q 和 p 的空和非空分为以下四种情况：

1 . q 空 ，p不空  2. q不空 ，p 空  3.  q 和 p都是空  4 ，q和p都不空 

首先，如果 q 和 p只有有一个为空，那么肯定为 false（一个空树，一个不空，不相同）

其次，如果 q 和 p 都为空，那么就是真，（空树也是相同的）

最后，我们判断q 和 p都不为空的情况，如果他们两个的值不相等，返回false，相等就继续迭代的向后走，同时判断左右子树是否相同。

代码如下：

bool isSameTree(struct TreeNode* p, struct TreeNode* q){    //如果两个都为空，返回true    if(p == NULL && q == NULL)    { return true;    }    //两者一个真，返回false    if(p == NULL || q == NULL)    { return false;    }    //两者都不为空，并且值不相等，返回false    if(p->val != q->val)    { return false;    } //同时迭代左子树和右子树，并且两者都为真    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);}

 101. 对称二叉树

对称二叉树讲解：

首先这道题是相同的数的进阶，我们要是用上面题目的代码协助完成。

 

代码如下：

//比较左右子树是否相同bool isSymmetricTree(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 isSymmetricTree(p->left,q->right) && isSymmetricTree(p->right,q->left);}bool isSymmetric(struct TreeNode* root){    if(root == NULL)    { return NULL;    }    return isSymmetricTree(root->left,root->right);}

 注意：

镜像比较，我们要一个左，一个右的比较，

又因为根节点本身就分左右树，

所以我们返回时应该返回两个

一个是左树的左树和右树的右树，

一个是左树的右数和右树的左树比较。

572. 另一棵树的子树

另一颗树的子树讲解：

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。（tree刚开始不为NULL）

思路：

简单来说就是找到每个子树，然后判断是否和subRoot是相同的树。

代码如下：

bool isSameTree(struct TreeNode* p, struct TreeNode* q){    //如果两个都为空，返回true    if(p == NULL && q == NULL)    { return true;    }    //两者一个真，返回false    if(p == NULL || q == NULL)    { return false;    }    //两者都不为空，并且值不相等，返回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){    //根节点初始不为NULL，后续访问到NULL，直接返回false    if(root == NULL)    { return false;    }    //从根节点开始判断，每个子树是否和subRoot是相同的子树。    if(isSameTree(root,subRoot))    { return true;    }    //如果左树和右树上有一个是和subRoot相同的子树就返回。    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);}