leetcode

0 class Solution {

1 public:

2 vector<TreeNode *> findDuplicateSubtrees(TreeNode *root) {

3 if (!root) return {};

4

5 unordered_map<string, vector<TreeNode *>> seen;

6 unordered_map<TreeNode *, string> um;

7 vector<TreeNode *> res;

8 stack<TreeNode *> st;

9

10 st.push(root);

11 um[nullptr] = "#";

12 while (!st.empty()) {

13 auto root = st.top();

14

15 if (um.count(root)) {

16 um[root] = to_string(root->val) + ' ' + um[root->left] + ' ' + um[root->right];

17 seen[um[root]].push_back(root);

18 st.pop();

19 continue;

20 }

21

22 um[root] = "";

23 if (root->right) st.push(root->right);

24 if (root->left) st.push(root->left);

25 }

26

27 for (const auto &[k, v] : seen)

28 if (v.size() > 1) res.push_back(v.back());

29

30 return res;

31 }

32 };