【C】链式二叉树算法题1 -- 单值二叉树

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

1  题目描述 

  如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。

示例 1：

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

示例 2：

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

  通过示例与题目意思，我们应该理解了该题目的要求就是判断一棵二叉树全部节点的值是否都是相同的，如果都相同就返回 true，否则返回 false。

2  算法解析 

  对于一棵二叉树来说，其相关算法题一般都可以考虑用递归算法来解决，因为一棵二叉树就是递归定义的嘛。这道题的解法有这么几种情况：

1） 当根节点为空时，此为一棵单值二叉树。

2） 当根节点不为空且其左孩子也不为空，但是根节点的值跟左孩子节点的值不相同，说明其不是一棵单值二叉树。

3） 当根节点不为空且其右孩子也不为空，但是根节点的值不与右孩子的值相同时，说明其也不是一棵单值二叉树。

4） 整棵树是一棵单值二叉树又可递归定义为根节点的左子树是一棵单值二叉树且其右子树也是一棵单值二叉树。

  其中 4）为递归过程，前三条为边界条件。

3  代码

typedef struct TreeNode TreeNode;
bool isUnivalTree(struct TreeNode* root) 
{
    //如果根结点为空，返回true
    if (root == NULL)
    {
        return true;
    }
    //如果左孩子不为空，且根节点值不等于左孩子的值，返回false
    if (root->left && root->val != root->left->val)
    {
        return false;
    }
    //如果右孩子不为空，且根节点值不等于右孩子的值，返回false
    if (root->right && root->val != root->right->val)
    {
        return false;
    }
    //判断左子树与右子树是否都是一棵相同的树
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}