如何进行单值二叉树

# 如何进行单值二叉树 ## 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. 测试用例设计

测试场景	示例树结构	预期结果
空树	null	True
单节点	[1]	True
全等树	[1,1,1]	True
不等树	[1,2,1]	False
深层不等	[1,1,1,null,2]	False

7. 性能对比

方法	时间复杂度	空间复杂度	适用场景
递归DFS	O(n)	O(h)	树深度较小
迭代BFS	O(n)	O(w)	需要避免递归
并行检查	O(n/p)	O(h)	大型平衡树

8. 总结

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

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

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