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

一、问题描述

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时，才返回 true；否则返回 false。 原题出自 965. 单值二叉树 - 力扣（LeetCode）

2de1c4d0dc7e4516a089d3fdef1954f2.jpeg

二、解题思路

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

• 如果节点为空，返回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);

}