设计一个分治算法来确定给定的两棵二叉树T1和T2是否相同。
时间: 2024-09-11 20:04:36 浏览: 97
设计一个分治算法来判断两棵二叉树是否相同,可以通过递归地比较两棵树的节点来进行。基本思路是,如果两棵树都为空,那么它们相同;如果其中一棵树为空,另一棵不为空,或者两棵树的根节点的值不相同,那么它们不相同;如果以上条件都不满足,那么需要递归地比较左右子树是否相同。
以下是分治算法的伪代码:
```
Function IsSameTree(T1, T2):
如果 T1 是空且 T2 是空:
返回 True
如果 T1 是空 或 T2 是空 或 T1 的值 不等于 T2 的值:
返回 False
左子树相同 = IsSameTree(T1 的左子树, T2 的左子树)
右子树相同 = IsSameTree(T1 的右子树, T2 的右子树)
返回 左子树相同 且 右子树相同
```
在实际编程中,需要将伪代码转换为具体的编程语言,比如Python、Java等。以下是Python语言的实现示例:
```python
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.val = value
self.left = left
self.right = right
def isSameTree(T1, T2):
if not T1 and not T2: # 如果两棵树都为空
return True
if not T1 or not T2 or T1.val != T2.val: # 如果其中一棵树为空,或者根节点值不同
return False
# 递归比较左右子树
return isSameTree(T1.left, T2.left) and isSameTree(T1.right, T2.right)
# 使用示例
# 构建两棵树,进行比较
# 树1: 1 树2: 1
# \ \
# 2 2
# / /
# 3 3
tree1 = TreeNode(1, TreeNode(2, TreeNode(3)))
tree2 = TreeNode(1, TreeNode(2, TreeNode(3)))
print(isSameTree(tree1, tree2)) # 输出: True
```
阅读全文