最新百度面试题（二）

题目：请实现两棵树是否相等的比较，相等返回，否则返回其他值，并说明算法复杂度。
数据结构为：
[pre]typedef struct_TreeNode{    char c;    TreeNode *leftchild;      TreeNode *rightchild;}TreeNode;[/pre]函数接口为：int CompTree(TreeNode* tree1,TreeNode* tree2);
注：A、B两棵树相等当且仅当Root->c==RootB–>c,而且A和B的左右子树相等或者左右互换相等。
解析：由题中对二叉树相等的定义判断可知，该题的解决思路是采用递归的方法，“而且A和B的左右子树相等或者左右互换相等”这句是最大的提示。因此我们不难写出程序，如下：
[pre]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;}[/pre]上面的代码是按照如果两棵树都是空的也认为是相同的二叉树。如果面试者要求，两个都为空的二叉树是不相同，那么上面的代码就是错误的了。
时间复杂度：从代码中可以看出，需要对两棵树都进行遍历，因此时间复杂度是O(N)

沙发自己的

板凳自己的

地板也是我的

难道这个是PHP，怎么看不懂