樹1 樹的同構
Problem statement:
問題陳述：
Write a function to detect if two trees are isomorphic. Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped.
編寫一個函數來檢測兩棵樹是否同構 。 如果通過一系列翻轉(即通過交換多個節點的左右子節點)可以從另一棵樹中獲得兩棵樹，則稱為同構樹。 任何級別的任何數量的節點都可以交換其子級。
Example1:
范例1：
These two trees are isomorphic
這兩個樹是同構的
Swap left child & right child of 1
交換左孩子和右孩子1
Swap left & right child of 5
交換5個左右孩子
Example 2:
范例2：
Solution:
解：
The conditions which needed to be satisfied are:
需要滿足的條件是：
Empty trees are isomorphic
空樹是同構的
Roots must be the same
根必須相同
Either left subtree & right subtree of one must be same with the same of other's, or left subtree of one must been same with right subtree of other's & right subtree of one must same with left subtree of other's.
一個的左子樹和右子樹必須與另一個的左子樹相同，或者一個的左子樹必須與另一個的右子樹相同，并且一個的右子樹必須與另一個的左子樹相同。
Pre-requisite:
先決條件：
Two Input binary trees (their roots actually), i.e., root1, root2
兩個輸入二叉樹(實際上是其根)，即，root1，root2
FUNCTION isIsomorphic(Node *root1,Node *root2)
1. Both are empty then it's isomorphic. //condition-1
IF (!root1 && !root2)
return true;
If particularly exactly one of them is empty,
then they can't be isomorphic.//extension of condition-1
IF(!root1 || !root2)
return false;
2. If root value are different, they can't be isomorphic//condition-2
IF(root1->data!=root2->data)
return false;
3. Check condition-3
Recursively checking subtrees
return ( ( isIsomorphic(root1->left,root2->left) &&
isIsomorphic(root1->right,root2->right) ) ||
(isIsomorphic(root1->right,root2->left) &&
isIsomorphic(root1->left,root2->right)));
END FUNCTION
C++ implementation
C ++實現
#include <bits/stdc++.h>
using namespace std;
// TreeNode node type
class TreeNode{
public:
int val; //value
TreeNode *left; //pointer to left child
TreeNode *right; //pointer to right child
};
// creating new node
TreeNode* newnode(int data)
{
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = data;
node->left = NULL;
node->right = NULL;
return(node);
}
// function to check isomorphic trees
bool isIsomorphic(TreeNode *root1,TreeNode *root2)
{
if(!root1 && !root2)
return true;
if(!root1 || !root2)
return false;
if(root1->val!=root2->val)
return false;
return ( (isIsomorphic(root1->left,root2->left) &&
isIsomorphic(root1->right,root2->right) )||
(isIsomorphic(root1->right,root2->left) &&
isIsomorphic(root1->left,root2->right)));
}
int main(){
cout<<"tree is built as per example-1\n";
TreeNode *root1=newnode(1);
root1->left= newnode(5);
root1->right= newnode(2);
root1->right->right=newnode(3);
root1->left->left=newnode(8);
root1->left->right=newnode(4);
TreeNode *root2=newnode(1);
root2->left= newnode(2);
root2->right= newnode(5);
root2->right->right=newnode(8);
root2->right->left=newnode(4);
root2->left->right=newnode(3);
if(isIsomorphic(root1,root2))
cout<<"They are isomorphic tree\n";
else
cout<<"They are not isomorphic tree\n";
cout<<"tree is built as per example-2\n";
TreeNode *root3=newnode(1);
root3->left= newnode(9);
root3->right= newnode(2);
root3->right->right=newnode(3);
root3->left->left=newnode(8);
root3->left->right=newnode(4);
if(isIsomorphic(root1,root3))
cout<<"They are isomorphic tree\n";
else
cout<<"They are not isomorphic tree\n";
return 0;
}
Output
輸出量
tree is built as per example-1
They are isomorphic tree
tree is built as per example-2
They are not isomorphic tree
Explanation with example
舉例說明
Let's check the example-1
讓我們看一下示例1
Nodes are represented by their respective values for better understanding
節點由各自的值表示，以便更好地理解
In the main we call isIsomorphic(root1,root2) //isIsomorphic(1,1)
------------------------------------------------
isIsomorphic(1,1)
root1 is not NULL
root2 is not NULL
root1->data==root2->data
thus it returns
((isIsomorphic(root1->left,root2->left) && isIsomorphic(root1->right,root2->right)) ||
(isIsomorphic(root1->right,root2->left) && isIsomorphic(root1->left,root2->right)));
i.e.,
((isIsomorphic(5,2) && isIsomorphic(2,5)) ||
(isIsomorphic(2,2) && isIsomorphic(5,5)));
Thus call to isIsomorphic(5,2), isIsomorphic(2,5),
isIsomorphic(2,2), isIsomorphic(5,5)
------------------------------------------------
isIsomorphic(5,2)
root1 is not NULL
root2 is not NULL
root1->data!=root2->data
thus it returns FALSE
------------------------------------------------
isIsomorphic(2,5)
root1 is not NULL
root2 is not NULL
root1->data!=root2->data
thus it returns FALSE
------------------------------------------------
isIsomorphic(2,2)
root1 is not NULL
root2 is not NULL
root1->data==root2->data
thus it returns
((isIsomorphic(root1->left,root2->left) && isIsomorphic(root1->right,root2->right) ) ||
(isIsomorphic(root1->right,root2->left) && isIsomorphic(root1->left,root2->right)));
i.e.,
((isIsomorphic(NULL,NULL) && isIsomorphic(3,3)) ||
(isIsomorphic(3,NULL) && isIsomorphic(NULL,3)));
Thus call to isIsomorphic(NULL,NULL), isIsomorphic(3,3),
isIsomorphic(3,NULL), isIsomorphic(NULL,3)
------------------------------------------------
isIsomorphic(NULL,NULL)
root1 is NULL
root2 is NULL
thus it return TRUE
------------------------------------------------
isIsomorphic(3,3)
root1 is not NULL
root2 is not NULL
root1->data==root2->data
thus it returns
((isIsomorphic(root1->left,root2->left) && isIsomorphic(root1->right,root2->right) ) ||
(isIsomorphic(root1->right,root2->left) && isIsomorphic(root1->left,root2->right)));
i.e.,
((isIsomorphic(NULL,NULL) && (isIsomorphic(NULL,NULL) ||
(isIsomorphic(NULL,NULL) && (isIsomorphic(NULL,NULL)));
Thus call to isIsomorphic(NULL,NULL), (isIsomorphic(NULL,NULL),
(isIsomorphic(NULL,NULL), (isIsomorphic(NULL,NULL))
All (isIsomorphic(NULL,NULL) returns TRUE
Thus, isIsomorphic(3,3) returns TRUE
------------------------------------------------
isIsomorphic(3,NULL)
exactly one root is empty
Thus it returns FALSE
------------------------------------------------
isIsomorphic(NULL,3)
exactly one root is empty
Thus it returns FALSE
------------------------------------------------
Thus ,
isIsomorphic(2,2)
=((isIsomorphic(NULL,NULL) && isIsomorphic(3,3) ) ||
(isIsomorphic(3,NULL) && isIsomorphic(NULL,3)))
=(TRUE && TRUE)|| (FALSE && FALSE)
=TRUE && FLASE
=TRUE
Same way, we can check that isIsomorphic(5,5) returns TRUE
------------------------------------------------
At main:
isIsomorphic(1,1)
=((isIsomorphic(5,2) && isIsomorphic(2,5)) ||
(isIsomorphic(2,2) && isIsomorphic(5,5)))
=((FALSE && FALSE)||(TRUE && TRUE)
=(FALSE && TRUE)
TRUE
Thus these two trees are isomorphic.
You can check the second example same way & can find returning FALSE
您可以以相同的方式查看第二個示例并找到返回的FALSE
翻譯自: https://www.includehelp.com/icp/check-if-tree-is-isomorphic.aspx
樹1 樹的同構
