数据结构 ——— 链式二叉树oj题：单值二叉树

题目要求

手搓一个单值二叉树

代码实现

题目要求

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false

手搓一个单值二叉树

代码演示：

// 数据类型
typedef int BTDataType;// 二叉树节点的结构
typedef struct BinaryTreeNode
{BTDataType data; //每个节点的数据struct BinaryTreeNode* left; //指向左子树的指针struct BinaryTreeNode* right; //指向右子树的指针
}BTNode;// 申请新节点
BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));// 判断是否申请成功if (newnode == NULL){perror("malloc fail");return NULL;}// 初始化newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}BTNode* CreatBinaryTree1()
{BTNode* n1 = BuyNode(1);assert(n1);BTNode* n2 = BuyNode(1);assert(n2);BTNode* n3 = BuyNode(1);assert(n3);BTNode* n4 = BuyNode(1);assert(n4);BTNode* n5 = BuyNode(1);assert(n5);BTNode* n6 = BuyNode(1);assert(n6);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;return n1;
}

代码实现

代码演示：

bool isUnivalTree(BTNode* root)
{if (root == NULL)return true;if (root->left != NULL && root->data != root->left->data)return false;if (root->right != NULL && root->data != root->right->data)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

代码解析：

第一个 if 语句是递归的结束条件之一，用于判断当前 root 是否为空，且根据第二个和第三个 if 语句来看，第一个 if 语句也可以作用于是否是单值的，如果不是单值的，那么第二个和第三个 if 语句就会返回 false，所以判断当前 root 是否是空的同时，也返回了当前判断的子树是单值
第二、三个 if 语句用于判断当前根节点的数据和左右子树的数据是否是单值，再根据递归转换 root ，具有传递性的判断是否是单值，如果不是，返回 false
最后通过递归，遍历 root 的左右子树，用 && 链接，因为当左子树不是单值时，就不用判断右子树，直接返回逻辑于后的结果

代码验证：

当二叉树是单值时：