(7)求两颗二叉树的相似 递归算法提示: 1)若T1和T2均为空,则返回值为1; 2)若T1和T2的深度均为1(即只有一个结点),则返回为1; 3)若T1的左子树和T2的左子树相似,并且T1的右子树和T2的右子树相似,则返回为1; 4)其它为返回值为0; 算法如下:
时间: 2024-11-20 09:35:40 浏览: 31
为了实现两颗二叉树B1和B2的相似性判断,你可以使用递归策略来遍历并对比它们的结构。这里是一个递归算法的Python实现,基于给出的题目描述[^1]:
```python
def are_trees_similar(t1, t2):
# 基本情况
if t1 is None and t2 is None:
return True # 空树相似
# 如果其中一个为空,但另一个不为空,它们不相似
if t1 is None or t2 is None:
return False
# 检查当前节点的左右子树是否都相似
if not are_trees_similar(t1.left, t2.left) or \
not are_trees_similar(t1.right, t2.right):
return False
# 如果到达这里,说明当前节点及其子树都相似,继续下一个节点
return True
# 示例用法
# 定义两个二叉树节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 创建两个示例二叉树
t1 = TreeNode(1)
t1.left = TreeNode(2)
t1.right = TreeNode(3)
t2 = TreeNode(1)
t2.left = TreeNode(2)
t2.right = TreeNode(3)
# 判断两个二叉树是否相似
result = are_trees_similar(t1, t2)
print(result) # 输出:True
```
阅读全文