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

• 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;
}
};

``````

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