algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

find-duplicate-subtrees.cpp (1275B)

      1 /**
      2  * Definition for a binary tree node.
      3  * struct TreeNode {
      4  *     int val;
      5  *     TreeNode *left;
      6  *     TreeNode *right;
      7  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
      8  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      9  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     10  * };
     11  */
     12 class Solution {
     13 public:
     14     
     15     unordered_map<string,int> subtrees {};
     16     vector<TreeNode*> matching {};
     17 
     18     string inOrder(TreeNode* root) {
     19         if(root == nullptr) {
     20             return "";
     21         }
     22         string current = "";
     23         string left = "L" + inOrder(root->left);
     24         current.append(left);
     25         current.append(to_string(root->val));
     26         current.append(", ");
     27         string right = "R" + inOrder(root->right);
     28         current.append(right);
     29 
     30         if(subtrees[current] == 0) {
     31             subtrees[current] += 1;
     32         } else {
     33             if (subtrees[current] == 1) {
     34                 subtrees[current] = 2; // won't be added to return again for multi-dupes
     35                 matching.push_back(root);
     36             }
     37         }
     38 
     39         return current;
     40     }
     41     
     42     vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
     43         inOrder(root);
     44         return matching;
     45     }
     46 };