【LeetCode】（二叉树）单值二叉树

水深无声 2022-11-29 05:41 133阅读 0赞

# 单值二叉树 #

## 题目描述 ##

*  题目：单值二叉树
 *  难度：简单
 *  题目描述：如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。
 *  示例一：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70_pic_center]
 *  示例二：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70_pic_center 1]

## 解题思路 ##

1.  用一个结点指针p指向root结点。
2.  如果p结点有左子树，就用p的data值与左子树的data值进行比对是否相等，然后递归访问左子树，用一个bool类型的左树标记来接收左树的情况
3.  如果p结点有右子树，就用p的data值与右子树的data值进行比对是否相等，然后递归访问右子树。用一个bool类型的右树标记来接收右树的情况
4.  最后返回左树标记与右树标记的&&运算结果

## 参考源码 ##

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
    bool isUnivalTree(struct TreeNode* root){ 
        if(root == NULL)
            return false;
        if(root->left == NULL && root->right == NULL)
            return true;
            
        struct TreeNode* p = root;
        bool flagRight = true;
        bool flagLeft = true;
        
        if(p->left != NULL)
        { 
            int leftValue = p->left->val;
            int rootValue = p->val;
            flagLeft =  (rootValue == leftValue) && isUnivalTree(p->left);
        }
        
        if(root->right != NULL)
        { 
            int rightValue = p->right->val;
            int rootValue = p->val;
            flagRight =  (rootValue == rightValue) && isUnivalTree(p->right);
        }
        
        return flagRight && flagLeft;
    }

## 复杂度分析 ##

![在这里插入图片描述][2020081913175573.png_pic_center]  
假设结点个数为n  
时间复杂度：O(n)  
空间复杂度：一次递归含最多需要：2个bool类型 + 4个int类型 + 1个结点类型，递归次数由结点个数决定，所以空间复杂度为O(n)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/c792e0da32f646f3ac73641f61a047ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/a0430e3d84254ffdb99616c0a5a6bb61.png
[2020081913175573.png_pic_center]: /images/20221124/1f7062a583eb4adca3f7e0de10f51eb3.png