怎么解析单值二叉树

# 怎么解析单值二叉树

## 目录
1. [什么是单值二叉树](#什么是单值二叉树)
2. [问题描述与示例](#问题描述与示例)
3. [递归解法](#递归解法)
4. [迭代解法](#迭代解法)
5. [复杂度分析](#复杂度分析)
6. [边界条件处理](#边界条件处理)
7. [实际应用场景](#实际应用场景)
8. [总结](#总结)

## 什么是单值二叉树

单值二叉树（Univalued Binary Tree）是指二叉树中所有节点的值都相同的特殊二叉树。这类树在数据校验、一致性检查等场景中有重要应用价值。

数学定义：
对于树中的任意节点 `node`，满足：
- `node.val == node.left.val`（如果左子节点存在）
- `node.val == node.right.val`（如果右子节点存在）

## 问题描述与示例

**LeetCode 965题**：给定一个二叉树的根节点 `root`，如果该树是单值二叉树则返回 `true`，否则返回 `false`。

示例1：

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

示例2：

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

## 递归解法

### 基本思路
递归是解决树问题的经典方法。我们可以通过比较当前节点值与子节点值来实现判断。

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isUnivalTree(root: TreeNode) -> bool:
    if not root:
        return True
    
    # 检查左子树
    if root.left:
        if root.val != root.left.val or not isUnivalTree(root.left):
            return False
    
    # 检查右子树
    if root.right:
        if root.val != root.right.val or not isUnivalTree(root.right):
            return False
    
    return True

优化版本

可以先将基准值存储，然后统一比较：

def isUnivalTree(root):
    def helper(node, value):
        if not node:
            return True
        if node.val != value:
            return False
        return helper(node.left, value) and helper(node.right, value)
    
    return helper(root, root.val)

迭代解法

广度优先搜索（BFS）

使用队列实现层次遍历：

from collections import deque

def isUnivalTree(root):
    if not root:
        return True
    
    queue = deque([root])
    target = root.val
    
    while queue:
        node = queue.popleft()
        if node.val != target:
            return False
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return True

深度优先搜索（DFS）

使用栈实现前序遍历：

def isUnivalTree(root):
    stack = [root]
    target = root.val
    
    while stack:
        node = stack.pop()
        if node.val != target:
            return False
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return True

复杂度分析

其中： - n 为节点总数 - h 为树的高度 - w 为树的最大宽度

边界条件处理

需要特别注意的特殊情况：

1. 空树处理：

   if not root:
      return True  # 或根据题目要求返回False
   

2. 单节点树：

   if not root.left and not root.right:
      return True
   

3. 不平衡树：

   • 左子树深度远大于右子树时，递归解法可能导致栈溢出

4. 大数比较：

   • 当节点值为浮点数时，应考虑精度问题

实际应用场景

1. 数据一致性校验：

   • 在分布式系统中检查多个副本数据是否一致

2. 图像处理：

   • 判断二值图像中连通区域是否纯色

3. 编译器设计：

   • 检查抽象语法树中所有节点是否属于同一类型

4. 游戏开发：

   • 判断游戏地图中某区域是否全部为相同地形

总结

解析单值二叉树的关键在于遍历所有节点并进行值比对。我们通过：

1. 递归法：代码简洁但需要注意栈深度
2. 迭代法：更适合大规模数据处理
3. 边界处理：确保算法鲁棒性

最终选择哪种方法取决于具体场景： - 对于高度平衡的树，递归更直观 - 对于深度较大的树，迭代更安全

# 终极解决方案（结合递归和基准值比较）
def isUnivalTree(root, value=None):
    if value is None:
        value = root.val
    if not root:
        return True
    return root.val == value and \
           isUnivalTree(root.left, value) and \
           isUnivalTree(root.right, value)

掌握单值二叉树的解析方法，不仅能够解决LeetCode题目，更能培养对树结构的基本操作能力，为处理更复杂的树形问题打下基础。 “`