首页 > 试题广场 >

请实现两棵树是否相等的比较，相等返回，否则返回其他值，并说明

[问答题]

请实现两棵树是否相等的比较，相等返回，否则返回其他值，并说明算法复杂度。
数据结构为：

typedef struct_TreeNode{
    char c;
    TreeNode *leftchild;
    TreeNode *rightchild;
}TreeNode;

函数接口为：int CompTree(TreeNode* tree1,TreeNode* tree2);
注：A、B两棵树相等当且仅当Root->c==RootB-->c,而且A和B的左右子树相等或者左右互换相等。

SunburstRun

 int compTree(TreeNode *tree1, TreeNode *tree2)
{
    if(!tree1 && !tree2) return 1;
    if((tree1 && !tree2) ||(!tree1 && tree2)) return 0;
    if(tree1 && tree2) 
    {
        if(tree1->c==tree2->c)
        {    
            if(compTree(tree1->leftChild, tree2->leftChild))
             return compTree(tree1->rightChild, tree2->rightChild);
            else if(compTree(tree1->rightChild, tree2->leftChild))
             return compTree(tree1->leftChild, tree2->rightChild);
        }
    }
    return 0; } 时间复杂度：从代码中可以看出，需要对两棵树都进行遍历，因此时间复杂度是O(N) 空间复杂度：应该是常数级别

编辑于 2015-06-27 07:40:19 回复(0)

反复横跳的豆乳蛋挞

bool _stdcall test(bt *t1,bt *t2)
{
    bool isEmpty1 = (t1 == NULL);
bool isEmpyt2 = (t2 == NULL);
if( isEmpyt1 == isEmpty2)
{
        return true;
}
if( isEmpty1 || isEmpty2)
{
        return false;
}
if(t1->data != t2->data)
{
        return false
}

return (test(t1->left,t2->right) && test(t1->right,t2->left)) ||
(test(t1->left,t2->left) && test(t1->right,t2->right));

}

发表于 2023-09-15 19:37:59 回复(0)

张超.

bool _stdcall test(bt *t1,bt *t2)
{
	bool isEmpty1 = (t1 == NULL);
    bool isEmpyt2 = (t2 == NULL);
    if( isEmpyt1 == isEmpty2)
    {
		return true;
    }
    if( isEmpty1 || isEmpty2)
    {
		return false;
    }
    if(t1->data != t2->data)
    {
		return false
    }
    
    return (test(t1->left,t2->right) && test(t1->right,t2->left)) ||
    (test(t1->left,t2->left) && test(t1->right,t2->right));
	
}

发表于 2016-03-30 20:07:24 回复(0)

牛客304487号

 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;  
    }

算法复杂度：

在树的第0层，有1个节点，进行1次函数调用；

在树的第1层，有2个节点，可能进行4次函数调用；

在树的第2层，有4个节点，我们可能进行16次函数调用；

....

在树的第x层，有2^x个节点，可能进行(2^x)^2次函数调用；

所以算法的复杂度为O(n^2)，空间复杂度为常数级别，即O（1）

编辑于 2015-06-27 11:03:46 回复(0)