编写程序判断树是否同构?其中同构是指给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则称两棵树是“同构”的,输出True,否则输出False。
时间: 2023-06-11 09:04:22 浏览: 153
这是一个经典的树同构判断问题,可以通过递归实现。具体步骤如下:
1. 如果 T1 和 T2 都是空树,则返回 True。
2. 如果 T1 和 T2 中只有一个为空树,则返回 False。
3. 如果 T1 和 T2 的根节点不相同,则返回 False。
4. 分别对 T1 和 T2 的左右子树进行比较:
- T1 的左子树与 T2 的左子树、T1 的右子树与 T2 的右子树相同,或者
- T1 的左子树与 T2 的右子树、T1 的右子树与 T2 的左子树相同。
5. 如果以上步骤都满足,则返回 True,否则返回 False。
具体的 Python 代码如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_isomorphic(t1: TreeNode, t2: TreeNode) -> bool:
if not t1 and not t2:
return True
elif not t1 or not t2:
return False
elif t1.val != t2.val:
return False
return (is_isomorphic(t1.left, t2.left) and is_isomorphic(t1.right, t2.right)) \
or (is_isomorphic(t1.left, t2.right) and is_isomorphic(t1.right, t2.left))
```
其中,TreeNode 表示树节点的类,包含 val、left、right 三个属性;is_isomorphic 函数就是判断两棵树是否同构的函数,直接调用即可。注意,这里的 TreeNode 类不是 Python 内置的类型,需要自定义实现。
阅读全文