如何优化好一个网站,自己做网站导航页,室内设计师排名,wordpress主题 windows live一、摘要
今天要讲的是leetcode单值二叉树#xff0c;这里用到的C语言#xff0c;主要提供的是思路#xff0c;大家看了我的思路之后可以点击链接自己试一下。
二、题目简介
如果二叉树每个节点都具有相同的值#xff0c;那么该二叉树就是单值二叉树。
只有给定的树是单…一、摘要
今天要讲的是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) {// 如果当前节点为空说明已经遍历到叶子节点的子节点返回 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);
} 大家可以代入一个中途不相同值的二叉树进行递归展开这个递归比较简单很好理解。 思路二迭代
递归方法虽然简洁但在某些情况下可能会受到递归深度的限制尤其是对于非常深的二叉树。我们可以使用迭代法来避免递归的开销。 使用一个队列来存储待访问的节点。 从根节点开始将根节点的值作为目标值。 遍历队列中的每个节点检查其值是否与目标值一致。 如果发现任意一个节点的值与目标值不同直接返回 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。
优点 避免递归使用迭代法避免了递归的深度限制问题。 逻辑清晰层次遍历的逻辑直观容易理解和实现。 高效时间复杂度为 O(n)其中 n 是树的节点数。
其实这道题思路和内容都挺简单的这道题还可以通过全局变量记录目标值或者DFS来实现我们在日常学习过程中都可以通过一题多解的方法来锻炼代码思考能力。好啦今天的leetcode每日一题就到这里啦
