查找两棵树是否同构

如果两棵树具有相似的结构，并且它们之间唯一的区别可能是，那么它们的子节点可能会或可能不会被交换，因此可以称它们为同构。例如：查找两棵树是否同构

 4     4 
/ \   / \ 
    2  6 and 6  2 
/\ /\  /\ /\ 
1 3 5 7  1 3 7 5

下面的代码应该是我在网上找到的正确的实现，但由于某种原因，它不适用于上述树。我做错了什么？

#include <iostream> 
using namespace std; 

class Node{ 

public: 

    Node * left; 
    Node * right; 
    int val; 

    Node(int v){ 
     left = NULL; 
     right = NULL; 
     val = v;  
    } 
}; 

bool isIsomorphic(Node* n1, Node *n2) 
{ 
// Both roots are NULL, trees isomorphic by definition 
if (n1 == NULL && n2 == NULL) 
    return true; 

// Exactly one of the n1 and n2 is NULL, trees not isomorphic 
if (n1 == NULL || n2 == NULL) 
    return false; 

if (n1->val != n2->val) 
    return false; 

// There are two possible cases for n1 and n2 to be isomorphic 
// Case 1: The subtrees rooted at these nodes have NOT been "Flipped". 
// Both of these subtrees have to be isomorphic, hence the && 
// Case 2: The subtrees rooted at these nodes have been "Flipped" 
return 
(isIsomorphic(n1->left,n2->left) && isIsomorphic(n1->right,n2->right))|| 
(isIsomorphic(n1->left,n2->right) && isIsomorphic(n1->right,n2->left)); 
} 

int main() 
{ 
Node * na_4 = new Node(4); 
Node * na_2 = new Node(2); 
Node * na_6 = new Node(6); 
Node * na_1 = new Node(1); 
Node * na_3 = new Node(3); 
Node * na_5 = new Node(5); 
Node * na_7 = new Node(7); 

na_4->left = na_2; 
na_4->right = na_6; 

na_2->left = na_1; 
na_2->right = na_3; 

na_6->left = na_5; 
na_6->right = na_7; 


Node * nb_4 = new Node(4); 
Node * nb_6 = new Node(6); 
Node * nb_2 = new Node(2); 
Node * nb_1 = new Node(1); 
Node * nb_3 = new Node(3); 
Node * nb_7 = new Node(7); 
Node * nb_5 = new Node(5); 

nb_4->left = nb_6; 
nb_4->right = nb_2; 

nb_6->left = nb_1; 
nb_6->right = nb_3; 

nb_2->left = nb_7; 
nb_2->right = nb_5; 


if(isIsomorphic(na_4, nb_4)){ 
    cout << "Yes they are isomorphic" << endl; 
} 
else 
{ 
    cout << "No there are not isomorphic" << endl; 
} 

return 0; 
}

它输出它们不是同构的。

来源

2014-01-31 user3256520

这些树不是同构的，由提供here的定义：

两棵树被称为同构，如果他们中的一个可以从其他一系列翻转来获得，通过交换左，右，即儿童的多个节点。任何级别的任意数量的节点都可以让他们的孩子交换。两棵空树是同构的。

如，在一棵树，2有子1和3，但在其他的树，2有儿童7和5

通过交换两个孩子，你实际上交换他们的整个子树，而不仅仅是那些节点，将所有其他的地方留下。

这两个，例如，将是同构：

来源

2014-01-31 14:37:26 Dukeling

这些树给出不同构。两棵树被称为同构当且仅当它们中的一个可以通过一系列翻转而从其他中获得，即通过交换许多节点的左右儿童。此外，任何级别的任意数量的节点都可以让其子节点交换。

来源

2014-02-01 19:28:27

查找两棵树是否同构

回答

相关问题