单值二叉树＜难度系数⭐＞

「这是我参与11月更文挑战的第22天，活动详情查看：2021最后一次更文挑战」

1、单值二叉树＜难度系数⭐＞

📝 题述：如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。

💨 示例 1：

输入：[1,1,1,1,1,null,1]

输出：true

💨 示例 2：

输入：[2,2,2,5,2]

输出：false

⚠ 注意：

1️⃣ 给定树的节点数范围是 [1, 100]。

2️⃣ 每个节点的值都是整数，范围为 [0, 99] 。

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：

在数学中大家都知道等号具有传递性，如 a = b , b = c，那么 a = c 。

那么这里

a == b && a == c

b == d && b == e

... ...

在每层栈帧中：如果那个节点为空返回 true；判断左右子树与根，如果不相等返回 false ；相等继续递归

leetcode原题

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int BTDataType;
typedef struct TreeNode 
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
}BTNode;
//单值二叉树
bool isUnivalTree(struct TreeNode* root) {
	if (root == NULL)
	{
		return true;
	}
	//左树不为空且左树不等于根val
	if (root->left && root->left->val != root->val)
	{
		return false;		
	}
	//右树不为空且右树不等于根val
	if (root->right && root->right->val != root->val)
	{
		return false;
	}
	//递归
	return isUnivalTree(root->left) && isUnivalTree(root->right);
}
//malloc空间
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->val = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
//创建树
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode('A');
	BTNode* node2 = BuyNode('A');
	BTNode* node3 = BuyNode('A');
	BTNode* node4 = BuyNode('A');
	BTNode* node5 = BuyNode('A');
	BTNode* node6 = BuyNode('A');

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->right = node6;

	return node1;
}

int main()
{
	BTNode* root = CreatBinaryTree();
	printf("%d\n", isUnivalTree(root));
	return 0;
}
复制代码