数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时装研究
法律研究在 C++ 中查找所有重复的子树
考虑我们有一个二叉树。我们需要查找树中是否存在一些重复的子树。假设我们有一个如下所示的二叉树 -
有两个大小为 2 的相同子树。在每个子树 D 中，BD 和 BE 也是重复的子树。我们可以通过使用树序列化和哈希处理来解决这个问题。我们将在哈希表中存储子树的中序遍历。我们将为叶节点插入开括号和闭括号。
示例
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;
const char MARKER = '$';
struct Node {
public:
char data;
Node *left, *right;
};
Node* getNode(char key) {
Node* newNode = new Node;
newNode->data = key;
newNode->left = newNode->right = NULL;
return newNode;
}
unordered_set<string> subtrees;
string inorder(Node* node, unordered_map<string, int>& map) {
if (!node)
return "";
string str = "(";
str += inorder(node->left, map);
str += to_string(node->data);
str += inorder(node->right, map);
str += ")";
if (map[str] == 1)
cout << node->data << " ";
map[str]++;
return str;
}
void duplicateSubtreeFind(Node *root) {
unordered_map<string, int> map;
inorder(root, map);
}
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');
duplicateSubtreeFind(root);
}输出
D E B
更新于： 24-10-2019
150 次浏览
广告