資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中判斷兩棵樹是否同構
在二叉樹中，每個節點包含兩個子節點，即左子節點和右子節點。假設我們有兩棵二叉樹，任務是檢查其中一棵樹是否可以透過翻轉另一棵樹的左側來獲得。
如果一棵樹可以透過翻轉另一棵樹的左側來獲得，則稱這兩棵樹是同構的。
例如
輸入-1
輸出：同構
解釋：給定的樹-2可以透過翻轉樹-1的左側獲得，因此這兩棵樹是同構的。
解決此問題的方法
解決此特定問題的遞迴方法是，一個布林函式將檢查兩棵樹的根節點。如果兩棵樹的根節點都為空或為 NULL，則返回 True，並遞迴檢查兩個根節點的資料是否相同。然後，我們將遞迴檢查樹的左節點和右節點。
- 為兩棵二叉樹建立節點。
- 布林函式 isIsomorphicTree(node*r1, node*r2) 獲取兩棵樹的根節點，並返回樹是否同構。
- 最初，如果樹為空或沒有任何節點，則返回 True。
- 如果根節點的子樹沒有翻轉，並且如果兩者都翻轉，則返回 True。
示例
#include<bits/stdc++.h>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
bool isIsomorphicTree(treenode * r1, treenode * r2) {
if (r1 == NULL and r2 == NULL) {
return true;
}
if (r1 == NULL or r2 == NULL) {
return false;
}
return (r1 -> data == r2 -> data && ((isIsomorphicTree(r1 -> left, r2 -> right) && isIsomorphicTree(r1 -> right, r2 -> left)) || (isIsomorphicTree(r1 -> left, r2 -> left) && isIsomorphicTree(r1 -> right, r2 -> right))));
}
int main() {
struct treenode * r1 = createNode(1);
r1 -> left = createNode(2);
r1 -> right = createNode(3);
r1 -> left -> left = createNode(4);
r1 -> left -> right = createNode(5);
r1 -> right -> left = createNode(6);
r1 -> left -> right -> left = createNode(7);
r1 -> left -> right -> right = createNode(8);
struct treenode * r2 = createNode(1);
r2 -> left = createNode(3);
r2 -> right = createNode(2);
r2 -> right -> left = createNode(4);
r2 -> right -> right = createNode(5);
r2 -> left -> right = createNode(6);
r2 -> right -> right -> left = createNode(8);
r2 -> right -> right -> right = createNode(7);
if (isIsomorphicTree(r1, r2)) {
cout << "Isomorphic" << endl;
} else {
cout << "Not an Isomorphic" << endl;
}
return 0;
}執行以上程式碼將生成以下輸出：
輸出
Isomorphic
解釋：給定的樹可以透過翻轉另一棵樹的左側獲得，因此它是同構的。
更新於： 2021年2月23日
299 次檢視
廣告