【数据结构与算法】单值二叉树的判断
【摘要】 如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时,才返回true;否则返回false。
实现思路:将每个节点看做是根结点,与他的左孩子和右孩子的值进行对比是否相同
目录
一、问题描述
如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时,才返回
true
;否则返回false
。
二、解题思路
实现思路:
将每个节点看做是根结点,与他的左孩子和右孩子的值进行对比是否相同
递归实现:
- 如果节点为空,返回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);
}
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)