单值二叉树-LeetCode

单值二叉树

🎯 问题描述

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。

💻 解题思路

思路一：基准值对比法

核心思想：整棵树的所有节点都必须等于根节点的值。我们在外部提取根节点的值作为基准，递归检查每一个节点是否等于该基准值。

代码实现

from typing import Optional

# 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:
        ans = root.val  # 提取根节点的值作为全局基准
        def dfs(node):
            if node is None:
                return True
            # 当前节点值必须等于基准值，且左右子树也必须满足条件
            return ans == node.val and dfs(node.right) and dfs(node.left)
        return dfs(root)
````

### 思路二：父子节点对比法（拓展思路）

**核心思想**：一棵树是单值的，当且仅当根节点的值等于左右子节点的值，且左右子树本身也是单值二叉树。

```python
class Solution:
    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        # 检查左子节点：如果存在，值必须与根节点相同
        if root.left and root.left.val != root.val:
            return False
        # 检查右子节点：如果存在，值必须与根节点相同
        if root.right and root.right.val != root.val:
            return False
            
        # 递归检查左右子树是否也满足单值条件
        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

📊 性能分析

• 时间复杂度：$O(n)$。其中 $n$ 是二叉树的节点数，每个节点都会被访问一次。
• 空间复杂度：$O(h)$。其中 $h$ 是二叉树的高度，主要为递归调用栈的空间开销。

💡 思考

这道题是二叉树递归入门的经典题。

1. 基准值法：逻辑非常直观，利用闭包传递基准值，代码极其简洁。
2. 父子对比法：不需要额外的外部变量，纯粹通过节点之间的父子关系进行递归判断，是另一种非常地道的树形 DP 思维。