LeetCode-652. Find Duplicate Subtrees

LeetCode-652. Find Duplicate Subtrees

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Example 1:

1 / \ 2 3 / / \ 4 2 4 / 4

The following are two duplicate subtrees:

2 / 4

and

4

Therefore, you need to return above trees' root in the form of a list.

题解：

本来用set发现没法去重，然后构造了一个JudgeNode结构体

然后。。

第一次ac结果。。448ms

class Solution {public: struct JudgeNode { TreeNode* t; string s; }; vector findDuplicateSubtrees(TreeNode* root) { vector ans; if (root == NULL) { return ans; } vector subtree; map mp; getAllSubtrees(root, subtree); int n = subtree.size(); vector tmp; for (int i = 0; i < n; i++) { JudgeNode* j = new JudgeNode(); j->t = subtree[i]; j->s = getString(subtree[i]); tmp.push_back(j); } for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (tmp[i]->s == tmp[j]->s) { mp.insert(pair(tmp[i]->s, tmp[i]->t)); } } } map::iterator it; for (it = mp.begin(); it != mp.end(); it++) { ans.push_back(it->second); } return ans; } static string getString (TreeNode* a) { string res; queue bfs; bfs.push(a); res+=a->val; while (bfs.empty() == false) { TreeNode* node = bfs.front(); bfs.pop(); if (node->left != NULL) { bfs.push(node->left); res += to_string(node->left->val); } else { res += 'x'; } if (node->right != NULL) { bfs.push(node->right); res += to_string(node->right->val); } else { res += 'x'; } } return res; } static void getAllSubtrees(TreeNode* root, vector &subtree) { queue bfs; bfs.push(root); while (bfs.empty() == false) { TreeNode* node = bfs.front(); subtree.push_back(node); bfs.pop(); if (node->left != NULL) { bfs.push(node->left); } if (node->right != NULL) { bfs.push(node->right); } } }};

还是低效率的解法。。。我的思路就是这样了。。能优化的都尽可能优化了还是168ms。。。

class Solution {public: vector findDuplicateSubtrees(TreeNode* root) { vector subtree; if (root == NULL) { return subtree; } map> mp; getAllSubtrees(root, subtree); int n = subtree.size(); for (int i = 0; i < n; i++) { string s = getString(subtree[i]); if (mp.find(s) != mp.end()) { mp[s].push_back(subtree[i]); } else { mp.insert(pair>(s, vector(1, subtree[i]))); } } subtree.clear(); map>::iterator it; for (it = mp.begin(); it != mp.end(); it++) { if (it->second.size() > 1) { subtree.push_back(it->second[0]); } } return subtree; } static string getString (TreeNode* a) { string res; queue bfs; bfs.push(a); res += a->val; while (bfs.empty() == false) { TreeNode* node = bfs.front(); bfs.pop(); if (node->left != NULL) { bfs.push(node->left); res += to_string(node->left->val); } else { res += 'x'; } if (node->right != NULL) { bfs.push(node->right); res += to_string(node->right->val); } else { res += 'x'; } } return res; } static void getAllSubtrees(TreeNode* root, vector &subtree) { queue bfs; bfs.push(root); while (bfs.empty() == false) { TreeNode* node = bfs.front(); subtree.push_back(node); bfs.pop(); if (node->left != NULL) { bfs.push(node->left); } if (node->right != NULL) { bfs.push(node->right); } } }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。