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

一、摘要

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

二、题目简介

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

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

示例 1：

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

示例 2：

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

提示：

1. 给定树的节点数范围是 [1, 100]。
2. 每个节点的值都是整数，范围为 [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) {// 如果当前节点为空，说明已经遍历到叶子节点的子节点，返回 trueif (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);
}

---

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

 思路二（迭代）

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

1. 使用一个队列来存储待访问的节点。

2. 从根节点开始，将根节点的值作为目标值。

3. 遍历队列中的每个节点，检查其值是否与目标值一致。

4. 如果发现任意一个节点的值与目标值不同，直接返回 false。

5. 如果所有节点都通过检查，最终返回 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
}

代码解释：

1. 队列初始化：

   • 使用一个数组 queue 作为队列，存储待访问的节点。

   • 使用两个指针 front 和 rear 分别表示队列的头部和尾部。

2. 目标值：

   • 将根节点的值作为目标值 target，所有节点的值都需要与它一致。

3. 层次遍历：

   • 从根节点开始，将其加入队列。

   • 每次从队列中取出一个节点，检查其值是否与目标值一致。

   • 如果一致，将其左右子节点（如果存在）加入队列。

   • 如果发现任意一个节点的值与目标值不同，直接返回 false。

4. 结束条件：

   • 如果队列为空，说明所有节点都已检查完毕，返回 true。

优点：

• 避免递归：使用迭代法避免了递归的深度限制问题。

• 逻辑清晰：层次遍历的逻辑直观，容易理解和实现。

• 高效：时间复杂度为 O(n)，其中 n 是树的节点数。

其实这道题思路和内容都挺简单的，这道题还可以通过全局变量记录目标值，或者DFS来实现，我们在日常学习过程中都可以通过一题多解的方法来锻炼代码思考能力。好啦今天的leetcode每日一题就到这里啦！