leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0652.cpp (909B)

      1 class Solution {
      2   public:
      3     vector<TreeNode *> findDuplicateSubtrees(TreeNode *root) {
      4         if (!root) return {};
      5 
      6         unordered_map<string, vector<TreeNode *>> seen;
      7         unordered_map<TreeNode *, string> um;
      8         vector<TreeNode *> res;
      9         stack<TreeNode *> st;
     10 
     11         st.push(root);
     12         um[nullptr] = "#";
     13         while (!st.empty()) {
     14             auto root = st.top();
     15 
     16             if (um.count(root)) {
     17                 um[root] = to_string(root->val) + ' ' + um[root->left] + ' ' + um[root->right];
     18                 seen[um[root]].push_back(root);
     19                 st.pop();
     20                 continue;
     21             }
     22 
     23             um[root] = "";
     24             if (root->right) st.push(root->right);
     25             if (root->left) st.push(root->left);
     26         }
     27 
     28         for (const auto &[k, v] : seen)
     29             if (v.size() > 1) res.push_back(v.back());
     30 
     31         return res;
     32     }
     33 };