【正确答案】
【答案解析】数据结构如下：
typedef struct_TreeNode
{
char c;
TreeNode*leftchild;
TreeNode*rightchild;
}TreeNode;
函数接口为int CompTree(TreeNode*tree1,TreeNode*tree2)。
注意：
A、B两棵树相等当且仅当rootA-＞c==rootB-＞c，而且A和B的左右子树相等或者左右互换相等。
可以采用递归的方式进行判断，具体算法如下：
int compTree(TreeNode *tree1, TreeNode *tree2)
{
if(!tree1 && !tree2)
return 1;
if((tree1 &&!tree2) ‖(!tree1 && tree2))
return 0;
if(tree1 && tree2)
{
if(tree 1-＞c= =tree2-＞c)
{
if(compTree(tree 1-＞leftehild, tree2-＞leftChild))
return compTree(tree 1-＞rightChild, tree2-＞rightChild);
else if(compTree(tree 1-＞rightChild, tree2-＞leffChild))
return compTree(tree 1-＞leffChild, tree2-＞rightChild);
}
}
return 0;
}
对于上述算法，在树的第0层，有1个结点，会进行1次函数调用；在树的第1层，有2个结点，可能会进行4次函数调用；在树的第2层，有4个结点，可能会进行16次函数调用……在树的第x层，有2
x
个结点，可能会进行(2
x
)
2
次函数调用；所以假设总结点数为n，则算法的复杂度为O(n
2
)。