当前位置：首页 > article >正文

单值二叉树（C语言详解版）

article 2025/1/30 3:49:07

一、摘要

今天要讲的是leetcode单值二叉树，这里用到的C语言，主要提供的是思路，大家看了我的思路之后可以点击链接自己试一下。

二、题目简介

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

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

示例 1：

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

示例 2：

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

提示：

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

三、思路分析

思路一（递归）

当我们看到这道题目时，一个直观的想法是通过递归遍历二叉树来解决问题。在遍历过程中，我们需要将每个节点的值与根节点的值进行比对。如果所有节点的值都与根节点一致，那么返回 true；否则返回 false。这种方法与递归实现二叉树的前序、中序或后序遍历有一定的相似性。因此，我们需要注意二叉树的结构特性，确保在遍历过程中，左子树和右子树都被完整地访问到。这是解决这道题的一个常见思路。

接下来，我将通过代码来展示这个思路的实现。

代码实现

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

bool isUnivalTree(struct TreeNode* root) {
    // 如果当前节点为空，说明已经遍历到叶子节点的子节点，返回 true
    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);
}

大家可以代入一个中途不相同值的二叉树，进行递归展开，这个递归比较简单很好理解。

思路二（迭代）

递归方法虽然简洁，但在某些情况下可能会受到递归深度的限制（尤其是对于非常深的二叉树）。我们可以使用迭代法来避免递归的开销。

使用一个队列来存储待访问的节点。
从根节点开始，将根节点的值作为目标值。
遍历队列中的每个节点，检查其值是否与目标值一致。
如果发现任意一个节点的值与目标值不同，直接返回 false。
如果所有节点都通过检查，最终返回 true。

代码实现：

#include <stdbool.h>
#include <stdlib.h>

/**
 * 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;  // 空树是单值二叉树

    int target = root->val;  // 目标值为根节点的值
    struct TreeNode* queue[100];  // 队列，假设最多100个节点
    int front = 0, rear = 0;

    queue[rear++] = root;  // 将根节点加入队列

    while (front < rear) {
        struct TreeNode* node = queue[front++];  // 出队
        if (node->val != target) return false;  // 如果当前节点值与目标值不同，直接返回false

        // 将左右子节点加入队列（如果存在）
        if (node->left) queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;
    }

    return true;  // 所有节点都通过检查，返回true
}

代码解释：

队列初始化：
- 使用一个数组 queue 作为队列，存储待访问的节点。
- 使用两个指针 front 和 rear 分别表示队列的头部和尾部。
目标值：
- 将根节点的值作为目标值 target，所有节点的值都需要与它一致。
层次遍历：
- 从根节点开始，将其加入队列。
- 每次从队列中取出一个节点，检查其值是否与目标值一致。
- 如果一致，将其左右子节点（如果存在）加入队列。
- 如果发现任意一个节点的值与目标值不同，直接返回 false。
结束条件：
- 如果队列为空，说明所有节点都已检查完毕，返回 true。