设计一个判断二叉树左右子树是否同构的算法
时间: 2024-05-12 18:16:11 浏览: 124
好的,这是一个计算机科学领域的问题,我可以为您解答。针对左右子树同构的问题,可以使用递归的做法来解决。具体做法是先判断两个根节点是否相同,如果相同,则递归判断左右子树是否同构,如果不同,则直接返回False。如果两棵子树都是空树,则返回True。以下是示例Python代码实现:
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_isomorphic(root1: TreeNode, root2: TreeNode) -> bool:
if not root1 and not root2:
return True
if not root1 or not root2:
return False
if root1.val != root2.val:
return False
return (is_isomorphic(root1.left, root2.left) and is_isomorphic(root1.right, root2.right)) or \
(is_isomorphic(root1.left, root2.right) and is_isomorphic(root1.right, root2.left))
```
这个算法的时间复杂度是O(n),其中n是树中节点的个数。
阅读全文