二叉树的讲解《五》（力扣习题讲解）

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

** 各位大帅哥，大漂亮**

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

可以一键三连支持博主

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

** **

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

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

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

​​​​​​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);
}

1. 对称二叉树

对称二叉树讲解：

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

代码如下：

//比较左右子树是否相同
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);
}

** 注意：**

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

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

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

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

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

1. 另一棵树的子树

另一颗树的子树讲解：

给你两棵二叉树 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);
}