Single-valued binary tree < difficulty factor ⭐ >

“This is the 22nd day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

1. Single-valued binary tree < difficulty factor ⭐ >

📝 description: a binary tree is a single-valued binary tree if every node has the same value. Returns true only if the given tree is a single-valued binary tree; Otherwise return false.

💨 Example 1:

Input: [1,1,1,1,1, null, 1]

Output: true,

💨 Example 2:

Input:,2,2,5,2 [2]

Output: false

⚠ note:

1 the range of node number of a given tree ️ is [1, 100].

2️ retail the value of each node is an integer and the range is [0, 99].

🧷 Platform: Visual Studio 2017 && Windows

🔑 Core Idea:

In mathematics, we all know that the equal sign is transitive, such as a = b, b = c, then a = c.

So here

a == b && a == c

b == d && b == e

. .

In each stack frame: returns true if that node is empty; Return false if left and right subtrees and roots are not equal; Equality continues to recurse

Leetcode the original

#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;
// single-valued binary tree
bool isUnivalTree(struct TreeNode* root) {
	if (root == NULL)
	{
		return true;
	}
	// The left tree is not empty and is not equal to the root val
	if(root->left && root->left->val ! = root->val) {return false;		
	}
	// The right tree is not empty and is not equal to the root of val
	if(root->right && root->right->val ! = root->val) {return false;
	}
	/ / recursion
	return isUnivalTree(root->left) && isUnivalTree(root->right);
}
/ / malloc space
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->val = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
/ / create a tree
BTNode* CreatBinaryTree(a)
{
	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(a)
{
	BTNode* root = CreatBinaryTree();
	printf("%d\n", isUnivalTree(root));
	return 0;
}
Copy the code