二叉树OJ题：LeetCode--965.单值二叉树-Toy模板网

这篇具有很好参考价值的文章主要介绍了二叉树OJ题：LeetCode--965.单值二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

朋友们、伙计们，我们又见面了，本期来给大家解读一下LeetCode中第965道二叉树OJ题，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

数据结构与算法专栏：数据结构与算法

个人主页 ：stackY、

C 语言专栏：C语言：从入门到精通

二叉树OJ题：LeetCode--965.单值二叉树,Leetcode刷题训练营,leetcode,算法,单值二叉树,c语言

LeetCode--965.单值二叉树： https://leetcode.cn/problems/univalued-binary-tree/

1.题目介绍

2.实例演示

3.解题思路

1.题目介绍

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

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

2.实例演示

3.解题思路

在此之前我们先来了解一下关于二叉树的一些基本的知识：二叉树的遍历

1. 前序遍历-->根节点、左子树、右子树

2. 中序遍历-->左子树、根节点、右子树

3. 后序遍历-->左子树、右子树、根节点

4. 层序遍历-->一层一层逐步遍历（借助于队列实现）

以上实现方法可以参考：二叉树的链式结构

要判断一颗树的所有结点都是同一个值（单值二叉树），首先想到的方法就是逐一遍历各各结点，然后进行比较判断，但是遍历求解二叉树的问题很容易出现错误，由于二叉树的问题最终都要归结为每一棵树的子问题，所以我们需要采用转化子问题的方法：

在这里需要注意一个问题：如果一棵树为空树，符不符合单值二叉树的条件呢？答案是符合的，因为空树的根和它的左右子树都是空，符合单值的条件。不为空树的话，如果它的左右子树都存在，并且左右子树的结点和根节点的值一样，那么再判断它的左右子树的左右子树，如果不一样，那么直接返回false......这样子以此类推，直到访问完整个二叉树。

代码演示：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


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