判断两棵二叉树是否同构。假设二叉树采二叉树链存储结构存放,设计一个递归算法判断两棵二叉树bt1和bt2是否同构
时间: 2024-06-20 21:04:14 浏览: 187
设一棵二叉树以二叉链表表示,试编写有关二叉树的递归算法
5星 · 资源好评率100%
判断两棵二叉树是否同构,需要判断它们的结构是否相同,即它们是否有相同的形态。如果它们有相同的形态,那么就是同构的。采用递归算法可以比较容易地解决这个问题。
具体实现过程如下:
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;
}
```
阅读全文