3、假设二叉树采用二叉链存储，，设计一个算法判断b1和b2表示的两棵二叉树是否相同。

可以使用递归的方式判断两棵二叉树是否相同。具体算法如下：

1. 如果两棵树都为空，返回 true。
2. 如果有一棵树为空，返回 false。
3. 如果两棵树根节点的值不相同，返回 false。
4. 递归判断左子树是否相同，如果不相同，返回 false。
5. 递归判断右子树是否相同，如果不相同，返回 false。
6. 如果以上都通过，返回 true。

算法实现如下：

bool isSameTree(TreeNode* b1, TreeNode* b2) {
    if (b1 == nullptr && b2 == nullptr) {
        return true;
    }
    if (b1 == nullptr || b2 == nullptr) {
        return false;
    }
    if (b1->val != b2->val) {
        return false;
    }
    return isSameTree(b1->left, b2->left) && isSameTree(b1->right, b2->right);
}

其中，TreeNode 是二叉树节点的结构体，包括一个 val 字段表示节点值，一个 left 字段表示左子树，一个 right 字段表示右子树。

相关问题

若已知两棵二叉树B1和B2皆为空，或者，皆不空且B1的左右子树和B2的左右子树分别相似，则称二叉树B1和B2相似。试编写算法判别给定两棵二叉树是否相似。

### 回答1：
可以使用递归的方法来判断两棵二叉树是否相似。具体思路如下：

1. 如果两棵二叉树都为空，则它们相似，返回 true。

2. 如果其中一棵二叉树为空，另一棵不为空，则它们不相似，返回 false。

3. 如果两棵二叉树的根节点的值不相等，则它们不相似，返回 false。

4. 递归判断两棵二叉树的左子树和右子树是否相似，如果都相似，则它们相似，返回 true，否则返回 false。

下面是具体的实现代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSimilar(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
    # 递归判断两棵二叉树的左子树和右子树是否相似
    return isSimilar(tree1.left, tree2.left) and isSimilar(tree1.right, tree2.right)

该算法的时间复杂度为 $O(n)$，其中 $n$ 是二叉树的节点数，因为需要遍历两棵二叉树的所有节点。空间复杂度为 $O(h)$，其中 $h$ 是二叉树的高度，因为使用递归栈空间来存储递归调用的信息。

### 回答2：
算法如下：

1. 若两棵二叉树均为空，则返回True。
2. 若两棵二叉树中有一棵为空，而另一棵不为空，则返回False。
3. 若两棵二叉树都不为空，则判断B1和B2对应节点的值是否相等：
a. 若不相等，则返回False。
b. 若相等，则分别对比B1的左右子树和B2的左右子树是否相似：
i. 若B1的左子树和B2的左子树相似，且B1的右子树和B2的右子树相似，则返回True。
ii. 若B1的左子树和B2的右子树相似，且B1的右子树和B2的左子树相似，则返回True。
iii. 若以上两种情况都不满足，则返回False。

下面是该算法的Python代码实现：

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def isSimilar(B1, B2):
if B1 is None and B2 is None:
return True
elif B1 is None or B2 is None:
return False
else:
if B1.val != B2.val:
return False
else:
return (isSimilar(B1.left, B2.left) and isSimilar(B1.right, B2.right)) or (isSimilar(B1.left, B2.right) and isSimilar(B1.right, B2.left))

# 测试样例
B1 = TreeNode(1)
B1.left = TreeNode(2)
B1.right = TreeNode(3)
B1.left.left = TreeNode(4)
B1.left.right = TreeNode(5)
B1.right.left = TreeNode(6)

B2 = TreeNode(1)
B2.left = TreeNode(3)
B2.right = TreeNode(2)
B2.left.left = TreeNode(6)
B2.right.left = TreeNode(5)
B2.right.right = TreeNode(4)

print(isSimilar(B1, B2)) # 输出True

### 回答3：
算法如下：

1. 编写一个函数`isSimilar`，该函数接受两个参数`B1`和`B2`，分别表示两棵二叉树。

2. 首先检查B1和B2是否都为空，如果是，则返回True，表示它们相似。

3. 然后检查B1和B2是否都不为空，如果是，则分别获取它们的左右子树B1_left, B1_right, B2_left, B2_right。

4. 利用递归调用`isSimilar(B1_left, B2_left)`判断B1_left和B2_left是否相似，如果不相似则返回False，否则继续。

5. 利用递归调用`isSimilar(B1_right, B2_right)`判断B1_right和B2_right是否相似，如果不相似则返回False，否则说明B1和B2相似。

完整的算法代码如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSimilar(B1, B2):
    if B1 is None and B2 is None:
        return True
    elif B1 is not None and B2 is not None:
        B1_left = B1.left
        B1_right = B1.right
        B2_left = B2.left
        B2_right = B2.right
        return isSimilar(B1_left, B2_left) and isSimilar(B1_right, B2_right)
    else:
        return False

这个算法的时间复杂度是O(n)，其中n是二叉树中节点的个数。

判断二叉树b1中是否有与b2相同的子树

好的，我可以帮助你解决这个问题。你需要先遍历二叉树B1，找到所有子树，然后再分别与B2进行比较。具体实现可以使用递归算法，判断当前节点的子树是否与B2相同，如果相同则返回true，否则继续在左右子树中进行查找。如果遍历完B1都没有找到与B2相同的子树，则返回false。需要注意的是，在比较时要考虑节点值、左右子树结构以及节点数等因素。