L14.【LeetCode笔记】单值二叉树

目录

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);
}

运行结果