数据结构
网络
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 个视图
广告