Update 652.Find-Duplicate-Subtrees_v2.cpp

wisdompeak · web-flow · commit 9ed6a7eb359b · 2021-07-25T21:38:06.000-07:00
diff --git a/Tree/652.Find-Duplicate-Subtrees/652.Find-Duplicate-Subtrees_v2.cpp b/Tree/652.Find-Duplicate-Subtrees/652.Find-Duplicate-Subtrees_v2.cpp
@@ -9,37 +9,37 @@
  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  * };
  */
- using LL = long long;
 class Solution {
-    vector<TreeNode*>rets;
-    unordered_map<LL, int>key2Id;
-    unordered_map<LL, int>key2count;
+    unordered_map<string, int> key2Id;
+    unordered_map<string, int> key2count;
+    vector<TreeNode*> rets;
 public:
     vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) 
     {
-        getID(root);
-        return rets;
+        getId(root);
+        return rets;        
     }
-
-    LL getID(TreeNode* node)
+    
+    int getId(TreeNode* node)
     {
         if (node==NULL) return 0;
-        LL key = (getID(node->left)<<32) + (getID(node->right)<<16) + node->val;
-
-        if (key2Id.find(key)==key2Id.end())
-        {                        
-            key2Id[key] = key2Id.size();
+        
+        string key = to_string(node->val) + "#" + to_string(getId(node->left)) + "#" + to_string(getId(node->right));
+        
+        if (key2Id.find(key) == key2Id.end())
+        {
+            key2Id[key] = key2Id.size()+1;
             key2count[key] = 1;
         }
         else
         {
-            key2count[key] += 1;            
+            key2count[key]+=1;
             if (key2count[key]==2)
             {
                 rets.push_back(node);
             }
         }
-
+        
         return key2Id[key];
     }
 };
