深圳市人才一体化综合服务平台_专业平台建设_南宁网站优化公司电话_时事新闻最新

目录

1.题目

2.分析

一个容易想到的方法

巧解方法:分而治之

代码

运行结果

---

1.题目

https://leetcode.cn/problems/univalued-binary-tree/description/

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

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

示例 1：

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

示例 2：

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

提示：

1. 给定树的节点数范围是 [1, 100]。
2. 每个节点的值都是整数，范围为 [0, 99] 。

代码模板

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool isUnivalTree(struct TreeNode* root) 
{    
}

2.分析

一个容易想到的方法

遍历整个二叉树的所有节点,将每个节点存储的val和整个二叉树的根节点的val的值进行比较,若不同则返回false

bool preorder(struct TreeNode* root,int val)
{if (root==NULL)return true;if (root->val!= val)return false;return preorder(root->left,val) && preorder(root->right,val);}bool isUnivalTree(struct TreeNode* root) 
{return preorder(root,root->val);
}

巧解方法:分而治之

分而治之思想的核心参见105.【C语言】数据结构之二叉树求总节点和第K层节点的个数文章

让根节点和其左右子树的节点的val比较,左右子树的节点的val比较又和其左右子树的节点的val比较……直到遇到空树为止

代码

1.先判断根节点是否为NULL,如果为NULL,返回true

2.节点的值等于val,继续执行;不等于val则返回false,因此if需要判断不等于val的情况

如何判断?给了根节点root,需要判断左节点的值和右节点的值(前提左右节点不为NULL)

左节点:(root->left)->val

右节点:(root->right)->val

写成if (root->left && root->left->val!=root->val)和if (root->right && root->right->val!=root->val)

如果左节点为NULL或右节点为NULL,不进行操作(原因是不违反规则),执行isUnivalTree(root->left)和isUnivalTree(root->right)

备注:不和整个二叉树的根节点比较,而是和对应的左右子树的根节点比较,利用相等的传递性

★★返回值的写法:左节点和右节点的值只要有一个不等于val,就返回false

"只要有一个不等于"可以使用逻辑与&&来表示

写成return isUnivalTree(root->left) && isUnivalTree(root->right);即可

只要有一个返回false,无论返回多少个false,运算结果都是false

(true && true && true &&...&& false &&...true && true==false)

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

运行结果