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


  • 0
    Y

    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;
        
        int addNode(TreeNode* now) {
            if (now == NULL) return -1; // level -1
            
            int levelLeft = addNode(now->left);
            int levelRight = addNode(now->right);
            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();
            addNode(root);
            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;
        }
    };
    

Log in to reply
 

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