leetcode

commit dbd05c3b893bc9de37d63b9903a90463d6e20f4a
parent 1c8546dddabe78e4617ec7df4ab08854b1090f7c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 28 Feb 2023 10:04:41 +0100

Daily Problem

Diffstat:
A
Problems/0652.cpp
 | 
34
++++++++++++++++++++++++++++++++++
M
README.md
 | 
3
++-

2 files changed, 36 insertions(+), 1 deletion(-)
diff --git a/Problems/0652.cpp b/Problems/0652.cpp
@@ -0,0 +1,34 @@
+class Solution {
+public:
+  vector<TreeNode *> findDuplicateSubtrees(TreeNode *root) {
+    if (!root) return {};
+
+    unordered_map<string, vector<TreeNode *>> seen;
+    unordered_map<TreeNode *, string> um;
+    vector<TreeNode *> res;
+    stack<TreeNode *> st;
+
+    st.push(root);
+    um[nullptr] = "#";
+    while (!st.empty()) {
+      auto root = st.top();
+
+      if (um.count(root)) {
+        um[root] =
+            to_string(root->val) + ' ' + um[root->left] + ' ' + um[root->right];
+        seen[um[root]].push_back(root);
+        st.pop();
+        continue;
+      }
+
+      um[root] = "";
+      if (root->right) st.push(root->right);
+      if (root->left) st.push(root->left);
+    }
+
+    for (const auto &[k, v] : seen)
+      if (v.size() > 1) res.push_back(v.back());
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -231,6 +231,7 @@ for solving problems.
 |  0416  |   Medium   | [Partition Equal Subset Sum](Problems/0416.cpp)                                                  |
 |  0417  |   Medium   | [Pacific Atlantic Water Flow](Problems/0417.cpp)                                                 |
 |  0424  |   Medium   | [Longest Repeating Character Replacement](Problems/0424.cpp)                                     |
+|  0427  |   Medium   | [Construct Quad Tree](Problems/0427.cpp)                                                         |
 |  0429  |   Medium   | [N-ary Tree Level Order Traversal](Problems/0429.cpp)                                            |
 |  0430  |   Medium   | [Flatten a Multilevel Doubly Linked list](Problems/0430.cpp)                                     |
 |  0433  |   Medium   | [Minimum Genetic Mutation](Problems/0433.cpp)                                                    |
@@ -278,6 +279,7 @@ for solving problems.
 |  0617  |    Easy    | [Merge Two Binary Trees](Problems/0617.cpp)                                                      |
 |  0621  |   Medium   | [Task Scheduler](Problems/0621.cpp)                                                              |
 |  0637  |    Easy    | [Average of Levels in Binary Tree](Problems/0637.cpp)                                            |
+|  0652  |   Medium   | [Find Duplicate Subtrees](Problems/0652.cpp)                                                     |
 |  0653  |    Easy    | [Two Sum IV - Input is a BST](Problems/0653.cpp)                                                 |
 |  0654  |   Medium   | [Maximum Binary Tree](Problems/0654.cpp)                                                         |
 |  0662  |   Medium   | [Maximum Width of Binary Tree](Problems/0662.cpp)                                                |
@@ -464,5 +466,4 @@ for solving problems.
 |  2477  |   Medium   | [Minimum Fuel Cost to Report to the Capital](Problems/2477.cpp)                                  |
 |  2492  |   Medium   | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp)                                  |
 |  2497  |   Medium   | [Maximum Star Sum of a Graph](Problems/2497.cpp)                                                 |
-|  0427  |   Medium   | [Construct Quad Tree](Problems/0427.cpp)                                                 |