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。

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

相关问题

6-3 求二叉树中最大和的路径（递归法） 分数 10 作者 王东 单位 贵州师范学院 求二叉树中最大和的路径。如下图中最大和路径为5 4 6。 QQ截图20210225175644.png

在计算机科学中，给定一个二叉树，求解其最大路径和通常涉及到动态规划的思想，尤其是递归方法。这个问题可以理解为从任意节点开始，沿着左子树和右子树的最大路径之和，最终到达叶子节点。这里的路径可以包含正负值。

对于递归解决方案，你可以按照以下步骤进行：

1. **基本情况**：如果节点为空，那么路径和就是0。这是递归的基础条件，防止无限循环。
2. **递归策略**：对于非空节点，计算两个子树的最大路径和，分别记作`leftMaxPath`和`rightMaxPath`。
3. **组合结果**：当前节点加上左右子树中的较大路径和（即`node.val + max(leftMaxPath, rightMaxPath)`），取两者中的较大值作为当前节点到叶子节点的最大路径和。这是因为我们可以选择包括当前节点或者继续沿左/右子树。
4. **返回最大值**：最后返回的是根节点到最远叶子节点的最大路径和。

下面是一个伪代码示例（假设有一个名为`Node`的二叉树节点类，其中包含`val`表示节点值，`left`和`right`表示子节点）:

def maxPathSum(node):
    if node is None:
        return 0
    leftMax = maxPathSum(node.left)
    rightMax = maxPathSum(node.right)
    
    # 计算当前节点与左、右子树各自路径和的最大值
    maxWithCurrent = node.val + max(leftMax, rightMax)

    # 返回当前节点参与后的最大路径和
    return max(maxWithCurrent, leftMax, rightMax)

判断两棵二叉树是否同构。假设二叉树采二叉树链存储结构存放，设计一个递归算法判断两棵二叉树bt1和bt2是否同构

判断两棵二叉树是否同构，需要判断它们的结构是否相同，即它们是否有相同的形态。如果它们有相同的形态，那么就是同构的。采用递归算法可以比较容易地解决这个问题。

具体实现过程如下：
1. 如果两棵二叉树都为空，则它们是同构的。
2. 如果只有一棵二叉树为空，则它们不是同构的。
3. 如果两棵二叉树的根节点值不同，则它们不是同构的。
4. 如果两棵二叉树的根节点值相同，则需要判断它们的左子树和右子树是否同构。
5. 判断左子树和右子树是否同构时，需要分别判断它们的左子树和右子树是否同构，或者左子树和右子树是否互相镜像。

下面是递归算法的示例代码：

bool isIsomorphic(TreeNode* bt1, TreeNode* bt2) {
    if (bt1 == nullptr && bt2 == nullptr) {
        return true;
    }
    if (bt1 == nullptr || bt2 == nullptr) {
        return false;
    }
    if (bt1->val != bt2->val) {
        return false;
    }
    bool left = isIsomorphic(bt1->left, bt2->left) && isIsomorphic(bt1->right, bt2->right);
    bool right = isIsomorphic(bt1->left, bt2->right) && isIsomorphic(bt1->right, bt2->left);
    return left || right;
}