LeetCode 题解工作台
单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是 单值 二叉树。 只有给定的树是单值二叉树时，才返回 true ；否则返回 false 。 示例 1： 输入： [1,1,1,1,1,null,1] 输出： true 示例 2： 输入： [2,2,2,5,2] 输出： false 提示： 给定树的节…
4
题型
6
代码语言
3
相关题
当前训练重点
简单 · 二分·树·traversal
答案摘要
我们记根节点的值为 ，然后设计一个函数 ，它表示当前节点的值是否等于 ，并且它的左右子树也是单值二叉树。 在函数 中，如果当前节点为空，那么返回 ，否则，如果当前节点的值等于 ，并且它的左右子树也是单值二叉树，那么返回 ，否则返回 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
示例 1：
输入：[1,1,1,1,1,null,1] 输出：true
示例 2：
输入：[2,2,2,5,2] 输出：false
提示：
- 给定树的节点数范围是
[1, 100]。 - 每个节点的值都是整数，范围为
[0, 99]。
解题思路
方法一：DFS
我们记根节点的值为 ，然后设计一个函数 ，它表示当前节点的值是否等于 ，并且它的左右子树也是单值二叉树。
在函数 中，如果当前节点为空，那么返回 ，否则，如果当前节点的值等于 ，并且它的左右子树也是单值二叉树，那么返回 ，否则返回 。
在主函数中，我们调用 ，并返回结果。
时间复杂度 ，空间复杂度 。其中 是树中的节点数目。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
def dfs(root: Optional[TreeNode]) -> bool:
if root is None:
return True
return root.val == x and dfs(root.left) and dfs(root.right)
x = root.val
return dfs(root)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(H) |
面试官常问的追问
外企场景- question_mark
Can the candidate handle tree traversal techniques and manage state tracking effectively?
- question_mark
Does the candidate understand the importance of comparing node values in binary trees?
- question_mark
Can the candidate clearly explain the time and space complexity of the solution?
常见陷阱
外企场景- error
Failing to correctly handle trees with multiple different node values.
- error
Confusing DFS and BFS traversal, leading to inefficient or incorrect solutions.
- error
Not addressing the space complexity of the recursive stack or queue.
进阶变体
外企场景- arrow_right_alt
Check for uni-valued binary trees with more complex structures, such as unbalanced trees.
- arrow_right_alt
Use a different tree traversal technique like iterative DFS to avoid stack overflow.
- arrow_right_alt
Optimize the space complexity by reducing the space required for traversal.