[C++] Hard-core solution (29ms)

• The idea is easy, we start traversing from the leaves to the root, checking level by level. We have a sperate cache to store if the previous level of nodes is a duplicate or not. A duplicate node must have the left/right child with the same id in the cache as another node.

``````class Solution {
public:
vector<list<TreeNode*>> nodes;
unordered_map<TreeNode*, int> checks;

if (now == NULL) return -1; // level -1

int level = max(levelLeft, levelRight) + 1; // leaf level = 0

if (nodes.size() <= level) {
nodes.push_back(list<TreeNode*>());
}
nodes[level].push_back(now);
return level;
}

static bool mycomp(const TreeNode* a, const TreeNode* b) {
return a->val < b->val;
}

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
nodes.clear();
checks.clear();
vector<TreeNode*> ret;
int id = 0;
checks[NULL] = id++; // dummy node
for (int i = 0; i < nodes.size(); i++) {
nodes[i].sort(mycomp);
for (auto it = nodes[i].begin(); it != nodes[i].end(); ) {
TreeNode* now = *it;
if (checks[now->left] > -1 && checks[now->right] > -1) { // find a candidate
auto cit = it;
cit++;
while (cit != nodes[i].end()) {
TreeNode* cmp = *cit;
if (now->val != cmp->val) break;
if (now->val == cmp->val && checks[now->left] > -1 && checks[now->right] > -1) {
if (checks[now->left] == checks[cmp->left] && checks[now->right] == checks[cmp->right]) { // find dup
if (checks.count(now) == 0) { // first time
ret.push_back(now);
checks[now] = id++;
}
checks[cmp] = checks[now];
}
}

if (checks.count(cmp) > 0) {
cit = nodes[i].erase(cit);
} else {
cit ++;
}
}

if (checks.count(now) == 0) { // not duplicate
checks[now] = -1;
}
it = nodes[i].erase(it);
} else {
checks[now] = -1;
it ++;
}
}
}
return ret;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.