C++编写算法判断两棵二叉树是否相等
笔试题目:C++编写算法判断两棵二叉树是否相等
题目:请实现两棵树是否相等的比较,相等返回0否则返回其他值。
解析:A、B两棵树相等,当且仅当RootA->c == RootB->c,而且A的左右子树对应相等或者左右互换后相等。
思想是使用分治的方法,先判断当前节点是否相等(需要处理为空、是否都为空、是否相等),如果当前节点不相等,直接返回两棵树不相等;如果当前节点相等,那么就递归的判断他们的'左右孩子是否相等。因为这里是普通的二叉树,所以A的左、右子树和B的右、左子树相等也是可以的。
C++代码:
#include
using namespace std;
typedef struct TreeNode{
char c;
struct TreeNode * left;
struct TreeNode * right;
};
/*判断两棵二叉树是否相等,如果相等返回0,如果不相等则返回1*/
int compareTree(TreeNode* tree1, TreeNode* tree2){
//用分治的方法做,比较当前根,然后比较左子树和右子树
bool tree1IsNull = (tree1==NULL);
bool tree2IsNull = (tree2==NULL);
if(tree1IsNull != tree2IsNull){
return 1;
}
if(tree1IsNull && tree2IsNull){
//如果两个都是NULL,则相等
return 0;
}
//如果根节点不相等,直接返回不相等,否则的话,看看他们孩子相等不相等
if(tree1->c != tree2->c){
return 1;
}
return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right))
|
(compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left))
;
}
-
考研现场确认的四大细节
下面是小编为大家整理的考研现场确认的四大细节,欢迎大家的阅读。一、带齐证件和材料:在11月10日之前,做好一切准备工作。一定记住,学校老师办公和现场确认都只有五天时间。现在有问题,还来得及处理,不要等到最后一天才发现有问题。现场确认就是为了核对考生信息,以防...
-
北京大学心理学2017考研参考书目
随着考研接近,各地考生们都在积极复习备考。各院校也开始公布了各自的考研参考资料。下面是小编为大家整理收集的北京大学心理学2017考研参考书目,仅供大家参考。北京大学心理学系已形成师资力量雄厚、学科设置齐全、专业人才层出不穷的教学、科研体系。北京大学...
-
2015考研复习心得:教你如何顺利走过考研路
不知不觉大半年时间过去了——大概9个月的时间,考研结束了。在前段时间查明分数之后,我的心中不禁生出了许多感想。总分421,数学141,政治77,英语64,专业课139。下面跟即将准备考研的学弟学妹们分享一下我的考研历程。一、数学对于考经济类的学生们来说,数学...
-
2015考研管理类综合逻辑真题详解:易出高分
2015考研初试部分科目已经结束,小编在第一时间提供2015考研管理类综合逻辑真题详解,供考生们参考!因为管理类综合的卷子是花卷,所以我们这里所说的题目跟你看到的题号可能不一样,而且每道题的选项很可能不同,也就是说你的A选项有可能是我的B选项,所以我们的题目大概...