如何进行单值二叉树

# 如何进行单值二叉树

## 1. 什么是单值二叉树

单值二叉树（Univalued Binary Tree）是指二叉树中所有节点的值都相同的特殊二叉树。这类二叉树具有以下特点：

- 所有左子树和右子树都是单值二叉树
- 根节点与所有子节点的值相同
- 空树也被视为单值二叉树

```mermaid
graph TD
    A[1] --> B[1]
    A --> C[1]
    B --> D[1]
    B --> E[1]
    C --> F[1]
    C --> G[1]

2. 判断单值二叉树的算法

2.1 递归深度优先搜索（DFS）

最直观的解法是使用递归遍历整棵树：

def is_unival_tree(root):
    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 is_unival_tree(root.left) and is_unival_tree(root.right)

时间复杂度：O(n)，需要访问所有节点
空间复杂度：O(h)，递归栈深度取决于树的高度

2.2 迭代广度优先搜索（BFS）

使用队列实现的迭代方案：

from collections import deque

def is_unival_tree(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

优点：避免递归栈溢出风险

3. 算法优化思路

3.1 提前终止机制

当发现任何节点不满足条件时立即返回：

def is_unival_tree(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 if root else None)

3.2 并行子树检查

对于多核系统可以考虑并行检查左右子树（伪代码）：

parallel_check(left) AND parallel_check(right)

4. 实际应用场景

1. 数据校验：验证数据库索引结构的完整性
2. 图像处理：判断二值图像中的连通区域
3. 网络路由：检查路由表的一致性

5. 扩展变种问题

5.1 统计单值子树数量

def count_unival_subtrees(root):
    count = 0
    
    def helper(node):
        nonlocal count
        if not node:
            return True
        
        left = helper(node.left)
        right = helper(node.right)
        
        if left and right:
            if (not node.left or node.left.val == node.val) and \
               (not node.right or node.right.val == node.val):
                count += 1
                return True
        return False
    
    helper(root)
    return count

5.2 允许N%差异的单值树

def is_almost_unival(root, threshold=0.1):
    if not root:
        return True
    
    target = root.val
    mismatch = 0
    total = 0
    
    stack = [root]
    while stack:
        node = stack.pop()
        if node.val != target:
            mismatch += 1
        total += 1
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return (mismatch / total) <= threshold

6. 测试用例设计

7. 性能对比

8. 总结

判断单值二叉树是二叉树基础操作的重要练习，通过这个问题可以深入理解： - 树的遍历方式（DFS/BFS） - 递归与迭代的转换 - 算法优化技巧 - 边界条件处理

建议读者在理解基础解法后，尝试解决统计单值子树数量的变种问题，以巩固学习效果。 “`

文章共计约950字，包含算法实现、优化思路、应用场景和扩展问题等内容，采用Markdown格式并包含Mermaid图表。可根据需要调整代码示例的语言（如改为Java/C++等）。