当前位置:C++技术网 > 资讯 > 数据结构笔记分享:31 判断两棵二叉树是否相等

数据结构笔记分享:31 判断两棵二叉树是否相等

更新时间:2016-01-17 20:02:41浏览次数:1+次

首先  给出树的数据结构


typedef struct_TreeNode{
	char c;
	TreeNode *leftchild;
  	TreeNode *rightchild;
}TreeNode;
A、B两棵树相等当且仅当Root->c==RootB–>c,而且A和B的左右子树相等或者左右互换相等。



int CompTree(TreeNode* tree1,TreeNode* tree2)
{
	if(tree1 == NULL && tree2 == NULL)
		return 1;

	if(tree1 != NULL && tree2 != NULL)
	{
		if(tree1->c == tree2->c)
		{
			if(CompTree(tree1->leftchild, tree2->leftchild) &&
				CompTree(tree1->rightchild, tree2->rightchild) ||
				CompTree(tree1->rightchild, tree2->leftchild) &&
				CompTree(tree1->leftchild, tree2->rightchild))
			{
				return 1;
			}
		}
	}

	return 0;
}

上面的代码是按照如果两棵树都是空的也认为是相同的二叉树。如果面试者要求,两个都为空的二叉树是不相同,那么上面的代码就是错误的了。

时间复杂度:从代码中可以看出,需要对两棵树都进行遍历,因此时间复杂度是O(N)