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 字段表示右子树。

相关问题

假设二叉树采用二叉链存储结构，设计一个算法判断一棵二叉树b的左、右子树是否同构

同构指的是两棵树在结构上完全相同，但是它们的节点值可以不同。因此，我们需要比较两棵树的结构而不是节点值。

我们可以通过递归比较左右子树的结构来判断两棵树是否同构。具体来说，我们可以设计一个递归函数 `isIsomorphic(TreeNode* t1, TreeNode* t2)`，用于比较两棵树的结构是否相同。函数的参数分别表示两棵树的根节点。

算法步骤如下：

1. 如果两棵树都为空，返回 true。
2. 如果有一棵树为空而另一棵树不为空，返回 false。
3. 如果两棵树的根节点的值不同，返回 false。
4. 比较 t1 的左子树和 t2 的左子树是否同构，以及 t1 的右子树和 t2 的右子树是否同构。如果两个条件都满足，返回 true，否则返回 false。

具体实现代码如下：

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

在主函数中，我们可以调用 `isIsomorphic` 函数判断两棵树是否同构。例如：

TreeNode* t1 = new TreeNode(1);
t1->left = new TreeNode(2);
t1->right = new TreeNode(3);
t1->left->left = new TreeNode(4);
t1->left->right = new TreeNode(5);

TreeNode* t2 = new TreeNode(1);
t2->left = new TreeNode(3);
t2->right = new TreeNode(2);
t2->right->left = new TreeNode(5);
t2->right->right = new TreeNode(4);

if (isIsomorphic(t1, t2)) {
    cout << "t1 and t2 are isomorphic" << endl;
} else {
    cout << "t1 and t2 are not isomorphic" << endl;
}

输出结果为：

t1 and t2 are isomorphic

因为 t1 和 t2 的左、右子树的结构完全相同，所以它们是同构的。

假设二叉树采用二叉链存储结构进行存储。设计一个算法采用分治法求一棵二叉树bt的高度

递归的思想可以很好地应用于二叉树高度的求解。如果二叉树为空，则高度为0。否则，树的高度为左子树高度与右子树高度的最大值加1。因此，可以采用分治法递归地求解左右子树的高度。

具体算法如下：

int height(BiTree bt) {
    if (bt == NULL) {
        return 0;
    }
    int left_height = height(bt->lchild);
    int right_height = height(bt->rchild);
    return max(left_height, right_height) + 1;
}

其中，max()函数返回两个参数中的最大值。算法的时间复杂度是O(n)，其中n是二叉树的节点数。