【数据结构】C语言算法练习题——单值二叉树的判定

题目链接：

力扣https://leetcode.cn/problems/univalued-binary-tree/solution/dan-zhi-er-cha-shu-by-leetcode-solution-15bn/

解题思路：

1. 空树也是单值二叉树

2. 可以先列出不符合单值二叉树的情形，最后则为单值二叉树

3. 根结点的访问：root -> val

4.  root 是地址，结构体的地址

代码实现（法一）：

/**
 * 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)
    {
        if(root->val != root->left->val || !isUnivalTree(root->left))
        /*1.首先这里的 || 当二叉树在遍历左子树和右子树时，只要发现根结点的值与左子树或右子树的结点不相同时，无需执行||后面的代码，
            直接返回false
          2.当执行到||后面的代码时，说明根结点的值与左（或右）子树的结点里的值相同，但是例如第一层与第二层的根结点与左（或右）子
            树相同不代表第三层与第二层，第四层与第三层......所以要用递归来判断二叉树中的所有层数是否满足题意
          3.而之所以 isUnivalTree()在调用时前面要加 ！号，是因为：
            ||前面的判定条件 root->val != root->left->val 这是根结点与左子树结点不相等，直接返回false ，因为||后面的判定条件
            是递归，所以要加上！来表示根结点与左（或右）子树的值不相同，这正好与非递归的判断方法相反，这样一来，！使其if（）里的
            真值为1，从而返回false*/
        return false;
    }

    if(root->right) //当遍历到结点为NULL时，不会进入下面的代码，因为他在if()里的真值为0
    {
        //root->right 还是地址
        if(root->val != root->right->val || !isUnivalTree(root->right))
        return false;
    }

    return true;

}

代码实现（法二）：

/**
 * 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)//左子树
    {
        if(root->val != root->left->val)

        return false;
    }

    if(root->right)//右子树
    {
        //root->right 还是地址
        if(root->val != root->right->val)
        return false;
    }

    return isUnivalTree(root->left)&&isUnivalTree(root->right);//递归

}

第二种方法把递归调用放到了最后，相比于第一种方法代码更容易读懂