一、题目

1、题目描述

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。
样例输入： [1,1,1,1,1,null,1]
样例输出： true

2、基础框架

• C语言 版本给出的基础框架代码如下：

bool isUnivalTree(struct TreeNode* root){
}

3、原题链接

LeetCode 965. 单值二叉树

二、解题报告

1、思路分析

根据单值二叉树的定义，所有值都必须相同，我们可以递归定义它：
1）空树是单值二叉树；
2）它的左子树必须是单值二叉树；
3）它的右子树必须是单值二叉树；
4）如果左子树非空，那么它的值应该和左子树的根相同；
5）如果右子树非空，那么它的值应该和右子树的根相同；

2、时间复杂度

由于需要把所有结点都遍历一遍，所以时间复杂度为 $O(n)$。

3、代码详解

bool isUnivalTree(struct TreeNode* root){
    if(root == NULL) {
        return true;                       // (1)
    }
    if(root->left) {
        if(root->val != root->left->val) {
            return false;                  // (2)
        } 
        if(!isUnivalTree(root->left)) {
            return false;                  // (3)
        }
    }
    if(root->right) {
        if(root->val != root->right->val) {
            return false;                  // (4)
        } 
        if(!isUnivalTree(root->right)) {
            return false;                  // (5)
        }
    }
    return true;
}

• $(1)$ 空树是单值二叉树；
• $(2)$ 如果左子树非空，那么它的值应该和左子树的根相同；
• $(3)$ 它的左子树必须是单值二叉树；
• $(4)$ 如果右子树非空，那么它的值应该和右子树的根相同；
• $(5)$ 它的右子树必须是单值二叉树；

三、本题小知识

递归时处理二叉树问题很好的手段。

四、加群须知

相信看我文章的大多数都是「 大学生 」，能上大学的都是「 精英 」，那么我们自然要「 精益求精 」，如果你还是「 大一 」，那么太好了，你拥有大把时间，当然你可以选择「 刷剧 」，然而，「 学好算法 」，三年后的你自然「 不能同日而语 」。
那么这里，我整理了「 几十个基础算法 」的分类，点击开启：

大致题集一览：





为了让这件事情变得有趣，以及「 照顾初学者 」，目前题目只开放最简单的算法「 枚举系列 」（包括：线性枚举、双指针、前缀和、二分枚举、三分枚举），当有 一半成员刷完「 枚举系列 」的所有题以后，会开放下个章节，等这套题全部刷完，你还在群里，那么你就会成为「 夜深人静写算法 」专家团的一员。
不要小看这个专家团，三年之后，你将会是别人望尘莫及的存在。如果要加入，可以联系我，考虑到大家都是学生，没有「 主要经济来源 」，在你成为神的路上，「 不会索取任何 」。
?联系作者，或者扫作者主页二维码加群，加入刷题行列吧?

?让天下没有难学的算法?
C语言免费动漫教程，和我一起打卡！?《光天化日学C语言》?
入门级C语言真题汇总?《C语言入门100例》?
几张动图学会一种数据结构?《画解数据结构》?
组团学习，抱团生长?《算法入门指引》?
竞赛选手金典图文教程?《夜深人静写算法》?