单值二叉树

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
• 掘金LV3用户 https://juejin.cn/user/1381426159953960
• 阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
• 华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目

965. 单值二叉树 - 力扣（LeetCode） (leetcode-cn.com)
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

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

示例 1：

输入：[1,1,1,1,1,null,1]
输出：true
示例 2：

输入：[2,2,2,5,2]
输出：false

提示：

给定树的节点数范围是 [1, 100]。
每个节点的值都是整数，范围为 [0, 99]

方法1：

*思想：*先判断根的左右子树的值是否和根的值一致，如果一致，则去递归判断左右子树是否是单值二叉树

a == b b == c ==> a == c

==操作符具有传递性

• 空树满足单值二叉树

  • if(root == NULL)
    {
        return true;
    }
    

• 如果根节点不为空 ，就拿根的值和左子树，右子树的值比较是否一致。如果一致，再去递归左子树和右子树

  • 左右子树未知是否存在，所以要判断左右子树是否为空

  ---

  这样写没意义，左子树相等了，还要看右子树是否相等 拿不到直接结果

  if(root->left!=NULL && root -> left->val == root->val)
  

  ---

  应该写成这样

  if(root->left && root->left->val != root->val)
  {
      retunn false; 
  }
  

代码

bool isUnivalTree(struct TreeNode* root)
{
    //空树是单值二叉树
    if(root == NULL)
    {
        return true;
    }
    //判断左子树的值是否和根的值一致
    //要判断左子树是否存在
    //不相等，直接返回false
    if(root->left && root->left->val != root->val)
    {
        return false;
    }
    
    //判断右子树的值是否和根的值一致
    //要判断右子树是否存在
    //不相等，直接返回false
    if(root->right && root->right->val != root->val)
    {
        return false;
    }
    
    //如果左子树，右子树的值和根结点的值一致，左子树和右子树还要作为根继续往下递归
    //要保证左右子树都是单值二叉树，所以用&&
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

方法2：

思路：用根节点的值和所有结点的值进行比较，类似前序遍历

代码

//前序遍历,找和根节点的值不同的结点
//遇到不相等的就返回1
int PreOrder(struct TreeNode* root,int val)
{
    //空树返回0
    if(root == NULL)
    {
        return 0;
    }
    //子树结点的值和根节点的值不相等，返回1
    if(root->val !=val)
    {
        return 1;
    }
    //递归左子树和右子树比较判断，是否有值不相同的结点
    return PreOrder(root->left,val)+PreOrder(root->right,val);
}
bool isUnivalTree(struct TreeNode* root)
{
    int val = root->val;
    //递归计数
    int tmp = PreOrder(root,val);//tmp接收左右子树有多少个结点的值和根节点的值不相同
    //如果tmp为0->所有结点完全相同->单值二叉树
    if(tmp == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
    
}

\