C++ Postorder traversal without serialization with explaination beat 95%


  • 0
    W

    We can solve this problem if each subtree can be assign a unique key and a global integer id incrementing from 0. The unique key of subtree can be represent as a tuple:
    (root->val, left subtree id, right subtree id).
    1. For empty tree, the unique id is 0 and the key is something that can never be found in a real tree like (INT_MAX,INT_MAX,INT_MAX) as it is almost impossible to have any subtree whose id is INT_MAX
    2. For leaf node, the key is just the (root->val, 0, 0) as both of its children are empty tree
    3. For other nodes, if we do a post-order traversal of the tree, we can always know the id of their children and therefore can form their key tuple. We can use this key tuple to find whether the subtree has already been found, otherwise assign a new id to it.

    struct Subtree {
        int v;
        int lid; // id for left subtree
        int rid; // id for right subtree
        Subtree(int x, int l, int r) : v(x), lid(l), rid(r) {}
        bool operator==(const Subtree &r) const {
            return v==r.v && lid==r.lid && rid==r.rid;
        }
    };
    struct Hasher {
        size_t operator() (const Subtree& k) const{
            size_t key=k.v;
            return (key<<32)+(k.lid^k.rid);
        }
      };   
    struct Comp {
        bool operator() (const Subtree& l, const Subtree& r) const {
            return l.v==r.v && l.lid==r.lid && l.rid==r.rid;
        }
      };
    
    class Solution {
    public:     
        unordered_map<Subtree, int, Hasher, Comp> fmap; // Subtree=>Subtree id map
        vector<int> count; // id => count map
        vector<TreeNode*> rmap; // subtree id => real root map
        int PostTraverse(TreeNode* root) {
            if (root==NULL)
                return 0;
            int lid = PostTraverse(root->left);
            int rid = PostTraverse(root->right);
            Subtree st(root->val, lid, rid);
            if (fmap.find(st)==fmap.end()) {
                // a new subtree is found
                int newid = count.size(); // new id is always the number of all subtrees traversed
                fmap[st] = newid;
                count.push_back(1);
                rmap.push_back(root);
            } else {
                // this subtree has been found
                count[fmap[st]]++;
            }
            return fmap[st];
        }
    
        vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {       
            fmap[Subtree(INT_MAX,INT_MAX,INT_MAX)] = 0; // id 0 indicates a NULL tree
            count.push_back(1); // count[0] = 1;
            rmap.push_back(NULL); // id 0 indicate null tree
            PostTraverse(root);
            vector<TreeNode*> res;
            for (int i=0; i<count.size(); ++i)
                if (count[i]>1)
                    res.push_back(rmap[i]);
            return res;   
        }
    };
    
    

Log in to reply
 

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