資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的對稱樹
假設我們有一個二叉樹，任務是檢查它是否構成自身的映象。對稱二叉樹構成其自身的映象。
例如
輸入-1
輸出
True
解釋
由於給定的二叉樹構成其自身的映象，因此輸出為 True。
輸入-2：
輸出
False
解釋
由於給定的二叉樹沒有構成其自身的映象，因此它不是對稱的。
解決此問題的方法
對稱二叉樹是一棵樹，它是其自身的映象，這意味著我們必須檢查樹的左右節點是否相同。
布林函式將首先檢查左節點和右節點。如果節點為空或為 NULL，則返回 True。對於其他情況，我們將檢查它是否有左或右子節點，然後它們必須相同，以便它成為對稱樹。
- 取一個包含根及其子節點的二叉樹。
- 布林輔助函式 helper(node*root1, node*root2) 獲取同一棵樹的兩個根，這有助於檢查左子節點和右子節點是否相同。
- 如果樹為空或為 NULL，則返回 True。
- 遞迴檢查樹的左節點和右節點是否相等。
- 如果不滿足上述所有條件，則返回 False。
示例
#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 helper(struct treenode * root1, struct treenode * root2) {
if (root1 == NULL and root2 == NULL)
return true;
if (root1 and root2 and root1 -> data == root2 -> data)
return (helper(root1 -> left, root2 -> right) and helper(root1 -> right, root2 -> left));
return false;
}
bool isSymmetry(struct treenode * root) {
return helper(root, root);
}
int main() {
struct treenode * root = NULL;
root = createNode(4);
root -> left = createNode(2);
root -> right = createNode(2);
root -> left -> right = createNode(7);
root -> left -> left = createNode(5);
root -> right -> left = createNode(5);
root -> right -> right = createNode(7);
if (isSymmetry(root)) {
cout << "True" << endl;
} else {
cout << "False" << endl;
}
return 0;
}執行以上程式碼將生成以下輸出：
輸出
False
解釋
由於給定的樹不是對稱的，因此我們得到輸出 False。
更新於： 2021年2月23日
569 次檢視
廣告