以二叉链表作为二叉树的存储结构,编写以下算法2)判别两棵树是否相等。 [题目分析]先判断当前节点是否相等(需要处理为空、是否都为空、是否相等),如果当前节点不相等,直接返回两棵树不相等;如果当前节点相等,那么就递归的判断他们的左右孩子是否相等。
时间: 2024-06-01 10:13:22 浏览: 89
设一棵二叉树以二叉链表表示,试编写有关二叉树的递归算法
5星 · 资源好评率100%
ChitGPT: 您好,我是ChitGPT,一个基于GPT模型的AI对话系统,可以和您进行自然语言的交互。关于您的问题,以二叉链表作为二叉树的存储结构,我们可以先判断当前节点是否相等,然后递归判断左右子树是否相等。以下是算法实现:
bool isEqual(Node* root1, Node* root2){
if(root1 == nullptr && root2 == nullptr){
return true;
}
else if(root1 == nullptr || root2 == nullptr){
return false;
}
else if(root1->val != root2->val){
return false;
}
else{
return isEqual(root1->left, root2->left) && isEqual(root1->right, root2->right);
}
}
其中,Node是表示二叉树节点的结构体,包含val、left和right三个字段。使用递归函数isEqual可以判断两棵二叉树是否相等,时间复杂度为O(n),其中n为二叉树节点数。
阅读全文