【数据结构与算法 经典例题】单值二叉树的判断

              💓 博客主页：倔强的石头的CSDN主页 

             📝Gitee主页：倔强的石头的gitee主页

   ⏩ 文章专栏：《数据结构与算法 经典例题》C语言

                                  期待您的关注

目录

一、问题描述

二、解题思路

三、C语言实现代码 

---

 

 

一、问题描述

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

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

 

原题出自

965. 单值二叉树 - 力扣（LeetCode）

 

二、解题思路

实现思路:
将每个节点看做是根结点，与他的左孩子和右孩子的值进行对比是否相同

 

递归实现：

• 如果节点为空，返回true
• 再进行判断
• 如果左孩子存在且左孩子的值不等于节点的值，返回false
• 如果右孩子存在且右孩子的值不等于节点的值，返回false
• 如果上述return都没有执行，说明这三个节点组成的树的值相同（如果左右孩子存在的话)，进一步判断以左右孩子为根的子树是否值相同。分别递归调用函数，传递左右孩子的地址，如果返回的值都为true，则返回true（只有一种情况会返回true，就是递归至节点为空）

 

 

三、C语言实现代码 

//单值二叉树
bool isUnivalTree(BTNode* root)
{if (root == NULL)return true;if (root->left && root->left->data != root->data)return false;if (root->right && root->right->data != root->data)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);}