forked from Pheonix-001/Hacktoberfest_2022
-
Notifications
You must be signed in to change notification settings - Fork 0
/
all_DuplicateSubtrees.cpp
68 lines (59 loc) · 1.37 KB
/
all_DuplicateSubtrees.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// C++ program to find averages of all levels
// in a binary tree.
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to
left child and a pointer to right child */
struct Node {
int data;
struct Node* left, *right;
};
string inorder(Node* node, unordered_map<string, int>& m)
{
if (!node)
return "";
string str = "(";
str += inorder(node->left, m);
str += to_string(node->data);
str += inorder(node->right, m);
str += ")";
// Subtree already present (Note that we use
// unordered_map instead of unordered_set
// because we want to print multiple duplicates
// only once, consider example of 4 in above
// subtree, it should be printed only once.
if (m[str] == 1)
cout << node->data << " ";
m[str]++;
return str;
}
// Wrapper over inorder()
void printAllDups(Node* root)
{
unordered_map<string, int> m;
inorder(root, m);
}
/* Helper function that allocates a
new node with the given data and
NULL left and right pointers. */
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver code
int main()
{
Node* root = NULL;
root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(2);
root->right->left->left = newNode(4);
root->right->right = newNode(4);
printAllDups(root);
return 0;
}