6-6 判断两棵二叉树是否同构(递归法) 分数 10 作者 王东 单位 贵州师范学院 判断

好的，你的问题是如何判断两棵二叉树是否同构（递归法）。

同构指的是两棵二叉树的结构相同，但是节点的值可以不同。这里给出递归法的代码实现：

def is_isomorphic(root1, root2):
    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))

在递归过程中，首先判断两个根节点是否为空，如果都为空，则返回 True。如果其中一个为空，则返回 False。接下来判断两个根节点的值是否相同，如果不相同，则返回 False。

如果两个根节点的值相同，那么就需要递归判断左子树和右子树是否同构，或者判断左子树和右子树是否交叉同构。只有两者之一成立，才返回 True，否则返回 False。

这样，就完成了判断两棵二叉树是否同构的递归实现。

相关问题

5-2 计算二叉树深度 分数 8 作者 王东 单位 贵州师范学院 计算二叉树深度。 #incl

计算二叉树的深度可以使用递归的方法来解决。首先，判断二叉树是否为空，如果为空则深度为0。如果不为空，则可以计算左子树的深度和右子树的深度，并取二者中较大的值加上1作为整个二叉树的深度。

具体步骤如下：

1. 判断二叉树是否为空。
- 如果为空，则返回深度为0。
- 如果不为空，则继续下一步。

2. 递归计算左子树的深度。
- 将二叉树的左子树作为根节点进行递归计算。
- 将递归返回的深度存储在一个变量中。

3. 递归计算右子树的深度。
- 将二叉树的右子树作为根节点进行递归计算。
- 将递归返回的深度存储在一个变量中。

4. 取左子树深度和右子树深度的最大值，并加上1作为整个二叉树的深度。
- 比较左子树深度和右子树深度的大小，取较大值。
- 将较大值加上1，作为整个二叉树的深度。

5. 返回整个二叉树的深度。

这样就能够计算出给定二叉树的深度。通过递归的方式，我们可以对二叉树的每个子树进行深度的计算，并最终得到整个二叉树的深度。

用递归和分治法思想，判断两个二叉树是否同构

判断两个二叉树是否同构可以使用递归和分治法思想，下面是两种实现方式：

1. 递归实现

递归实现的思路是分别判断两个二叉树的左子树和右子树是否同构，如果左右子树都同构，则判断两个二叉树的根节点是否相同。代码如下：

def is_isomorphic(root1, root2):
    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))

2. 分治实现

分治实现的思路是将两个二叉树分别划分成左子树和右子树，然后递归判断左子树和右子树是否同构，最后判断两个二叉树的根节点是否相同。代码如下：

def is_isomorphic(root1, root2):
    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))
           
def is_isomorphic_dc(root1, root2):
    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_dc(root1.left, root2.left) and \
           is_isomorphic_dc(root1.right, root2.right) and \
           is_isomorphic_dc(root1.left, root2.right) and \
           is_isomorphic_dc(root1.right, root2.left)

以上两种方法都可以判断两个二叉树是否同构，其中递归实现的代码比较简洁，分治实现的代码稍微复杂一些，但是思路清晰。