编写程序判断树是否同构?其中同构是指给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则称两棵树是“同构”的,输出True,否则输出False。
时间: 2023-06-08 18:09:28 浏览: 185
好的,我理解了您的问题,请等待我给出答案。
判断两棵树是否同构,可以使用递归的方法。首先判断根节点是否相同,如果不同返回False,如果相同则分别递归左子树和右子树,判断左子树和右子树是否同构。需要注意的是,如果一棵树的左子树与另一棵树的右子树同构,右子树与另一棵树的左子树同构,则这两棵树是同构的。
以下是具体的实现方法,可供参考:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_isomorphic(tree1, tree2):
if not tree1 and not tree2:
return True
if not tree1 or not tree2:
return False
if tree1.val != tree2.val:
return False
# 判断左子树和右子树是否同构
is_left_isomorphic = is_isomorphic(tree1.left, tree2.right)
is_right_isomorphic = is_isomorphic(tree1.right, tree2.left)
# 如果一棵树的左子树与另一棵树的右子树同构,右子树与另一棵树的左子树同构,则这两棵树是同构的
is_left_right_isomorphic = is_isomorphic(tree1.left, tree2.left) and is_isomorphic(tree1.right, tree2.right)
return is_left_isomorphic and is_right_isomorphic or is_left_right_isomorphic
# 示例
# 构造两棵树
T1 = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
T2 = TreeNode(1, TreeNode(3, TreeNode(7), TreeNode(6)), TreeNode(2, TreeNode(5), TreeNode(4)))
# 判断两棵树是否同构
print(is_isomorphic(T1, T2)) # 输出True
```
希望这个答案能够帮到您!
阅读全文