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

发表于

「这是我参与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 ；相等继续递归

❗ 官方(仅供参考) ❕

方法一：深度优先搜索

  深度优先搜索，获取这颗树中的所有节点的值。然后，就可以判断所有节点的值都相等了。

方法二：递归

  一颗树是单值的，当且仅当根节点的子节点所在的子树也是单值的，同时根节点的值与子节点的值相同。这里使用递归实现这个判断的过程。left_correct 表示当前节点的左孩子是正确的，也就是说：左孩子所在的子树是单值的，并且当前节点的值等于左孩子的值。right_correct 对当前节点的右孩子表示同样的事情。递归处理之后，当根节点的这两种属性都为真的时候，我们就可以判定这颗二叉树是单值的。

leetcode原题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
c复制代码#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) {
        //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;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%