965. 单值二叉树

🟢   🔖  树 深度优先搜索 广度优先搜索 二叉树  🔗 力扣 LeetCode

题目

A binary tree is uni-valued if every node in the tree has the same value.

Given the root of a binary tree, return true _if the given tree is uni-valued , or _false otherwise.

Example 1:

Input: root = [1,1,1,1,1,null,1]

Output: true

Example 2:

Input: root = [2,2,2,5,2]

Output: false

Constraints:

• The number of nodes in the tree is in the range [1, 100].
• 0 <= Node.val < 100

题目大意

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

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

示例 1：


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

输出： true

示例 2：


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

输出： false

提示：

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

解题思路

可以通过深度优先搜索（DFS）遍历树的每个节点来完成判断

• 根节点的值 root.val 被保存为基准值，用于与其他节点的值比较。
• 使用递归方法，从根节点开始，依次检查左子树和右子树的所有节点。
• 如果当前节点为 null，说明已经遍历到了树的末尾，返回 true。
• 如果遇到某个节点的值与根节点的值不同，则立即返回 false。
• 如果所有节点的值都相同，则最终返回 true。

复杂度分析

• 时间复杂度: O(n)，其中 n 是树中节点的个数，每个节点访问一次。
• 空间复杂度: O(h)，其中 h 是树的高度，递归调用栈的最大深度与树的高度有关。

代码

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isUnivalTree = function (root) {
	const num = root.val; // 保存根节点的值作为基准值
	const dfs = (root) => {
		if (!root) return true; // 空节点默认返回 true
		if (root.val !== num) return false; // 如果当前节点值不同，返回 false
		return dfs(root.left) && dfs(root.right); // 递归检查左右子树
	};
	return dfs(root); // 调用递归函数从根节点开始检查
};

相关题目

题号	标题	题解	标签	难度	力扣
1469	寻找所有的独生节点 🔒		树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗