資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究檢查二叉樹是否包含兩個或更多大小的重複的子樹（C++）
考慮我們有一個二叉樹。我們必須查詢該樹中是否有兩個或更多大小的重複子樹。假設我們有一個如下所示的二叉樹 −
有兩個大小為 2 的相同子樹。我們可以使用樹序列化和雜湊程序來解決此問題。這個思想是將子樹序列化成字串，並將其儲存在雜湊表中。一旦我們找到一個不是葉子的序列化樹，並且它已經存在於雜湊表中，則返回 true。
示例
#include <iostream>
#include <unordered_set>
using namespace std;
const char MARKER = '$';
struct Node {
public:
char key;
Node *left, *right;
};
Node* getNode(char key) {
Node* newNode = new Node;
newNode->key = key;
newNode->left = newNode->right = NULL;
return newNode;
}
unordered_set<string> subtrees;
string duplicateSubtreeFind(Node *root) {
string res = "";
if (root == NULL) // If the current node is NULL, return $
return res + MARKER;
string l_Str = duplicateSubtreeFind(root->left);
if (l_Str.compare(res) == 0)
return res;
string r_Str = duplicateSubtreeFind(root->right);
if (r_Str.compare(res) == 0)
return res;
res = res + root->key + l_Str + r_Str;
if (res.length() > 3 && subtrees.find(res) != subtrees.end()) //if subtree is present, then return blank string return "";
subtrees.insert(res);
return res;
}
int main() {
Node *root = getNode('A');
root->left = getNode('B');
root->right = getNode('C');
root->left->left = getNode('D');
root->left->right = getNode('E');
root->right->right = getNode('B');
root->right->right->right = getNode('E');
root->right->right->left= getNode('D');
string str = duplicateSubtreeFind(root);
if(str.compare("") == 0)
cout << "It has dublicate subtrees of size more than 1";
else
cout << "It has no dublicate subtrees of size more than 1" ;
}輸出
It has dublicate subtrees of size more than 1
更新時間：2019 年 10 月 22 日
153 個檢視
廣告