题目要求
思路一:dfs+序列化
- 设计一种规则将所有子树序列化,保证不同子树的序列化字符串不同,相同子树的序列化串相同。
- 用哈希表存所有的字符串,统计出现次数即可。
- 定义map中的关键字(
key
)为子树的序列化结果,值(value
)为出现次数。
- 定义map中的关键字(
- 此处采用的方式是在dfs遍历顺序下的每个节点后添加"-",遇到空节点置当前位为空格。
java
class solution { map<string, integer> map = new hashmap<>(); list<treenode> res = new arraylist<>(); public list<treenode> findduplicatesubtrees(treenode root) { dfs(root); return res; } string dfs(treenode root) { if (root == null) return " "; stringbuilder sb = new stringbuilder(); sb.append(root.val).append("-"); sb.append(dfs(root.left)).append(dfs(root.right)); string sub = sb.tostring(); // 当前子树 map.put(sub, map.getordefault(sub, 0) + 1); if (map.get(sub) == 2) // ==保证统计所有且只记录一次 res.add(root); return sub; } }
- 时间复杂度:o(n^2)
- 空间复杂度:o(n)
c++
- 要把节点值转换为字符串格式……呜呜呜卡了半天才意识到
class solution { public: unordered_map<string, int> map; vector<treenode*> res; vector<treenode*> findduplicatesubtrees(treenode* root) { dfs(root); return res; } string dfs(treenode* root) { if (root == nullptr) return " "; string sub = ""; sub += to_string(root->val); // 转换为字符串!!! sub += "-"; sub += dfs(root->left); sub += dfs(root->right); if (map.count(sub)) map[sub]++; else map[sub] = 1; if (map[sub] == 2) // ==保证统计所有且只记录一次 res.emplace_back(root); return sub; } };
- 时间复杂度:o(n^2)
- 空间复杂度:o(n)
rust
- 在判定等于222的地方卡了好久,报错
borrow of moved value sub
,没认真学rust导致闭包没搞好,然后根据报错内容猜了下,把上面的加了个clone()
果然好了。
use std::rc::rc; use std::cell::refcell; use std::collections::hashmap; impl solution { pub fn find_duplicate_subtrees(root: option<rc<refcell<treenode>>>) -> vec<option<rc<refcell<treenode>>>> { let mut res = vec::new(); fn dfs(root: &option<rc<refcell<treenode>>>, map: &mut hashmap<string, i32>, res: &mut vec<option<rc<refcell<treenode>>>>) -> string { if root.is_none() { return " ".to_string(); } let sub = format!("{}-{}{}", root.as_ref().unwrap().borrow().val, dfs(&root.as_ref().unwrap().borrow().left, map, res), dfs(&root.as_ref().unwrap().borrow().right, map, res)); *map.entry(sub.clone()).or_insert(0) += 1; if map[&sub] == 2 { // ==保证统计所有且只记录一次 res.push(root.clone()); } sub } dfs(&root, &mut hashmap::new(), &mut res); res } }
- 时间复杂度:o(n^2)
- 空间复杂度:o(n)
思路二:dfs+三元组
- 和上面其实差不多,三元组本质上也是一种序列化形式,可以指代唯一的子树结构:
- 三元组中的内容为(根节点值,左子树标识,右子树标识)(根节点值, 左子树标识,右子树标识)(根节点值,左子树标识,右子树标识);
- 这个标识是给每个不同结构的子树所赋予的唯一值,可用于标识其结构。
- 所以三元组相同则判定子树结构相同;
- 该方法使用序号标识子树结构,规避了思路一中越来越长的字符串,也减小了时间复杂度。
- 三元组中的内容为(根节点值,左子树标识,右子树标识)(根节点值, 左子树标识,右子树标识)(根节点值,左子树标识,右子树标识);
- 定义哈希表mapmapmap存储每种结构:
- 关键字为三元组的字符串形式,值为当前子树的标识和出现次数所构成的数对。
- 其中标识用从000开始的整数flagflagflag表示。
java
class solution { map<string, pair<integer, integer>> map = new hashmap<string, pair<integer, integer>>(); list<treenode> res = new arraylist<>(); int flag = 0; public list<treenode> findduplicatesubtrees(treenode root) { dfs(root); return res; } public int dfs(treenode root) { if (root == null) return 0; int[] tri = {root.val, dfs(root.left), dfs(root.right)}; string sub = arrays.tostring(tri); // 当前子树 if (map.containskey(sub)) { // 已统计过 int key = map.get(sub).getkey(); int cnt = map.get(sub).getvalue(); map.put(sub, new pair<integer, integer>(key, ++cnt)); if (cnt == 2) // ==保证统计所有且只记录一次 res.add(root); return key; } else { // 首次出现 map.put(sub, new pair<integer, integer>(++flag, 1)); return flag; } } }
- 时间复杂度:o(n)
- 空间复杂度:o(n)
c++
class solution { public: unordered_map<string, pair<int, int>> map; vector<treenode*> res; int flag = 0; vector<treenode*> findduplicatesubtrees(treenode* root) { dfs(root); return res; } int dfs(treenode* root) { if (root == nullptr) return 0; string sub = to_string(root->val) + to_string(dfs(root->left)) + to_string(dfs(root->right)); // 当前子树 if (auto cur = map.find(sub); cur != map.end()) { // 已统计过 int key = cur->second.first; int cnt = cur->second.second; map[sub] = {key, ++cnt}; if (cnt == 2) // ==保证统计所有且只记录一次 res.emplace_back(root); return key; } else { // 首次出现 map[sub] = {++flag, 1}; return flag; } } };
- 时间复杂度:o(n)
- 空间复杂度:o(n)
rust
- 三元组不好搞,所以用了两个二元哈希表替代一个存放三元组和标识,另一个存放标识与出现次数。
use std::rc::rc; use std::cell::refcell; use std::collections::hashmap; impl solution { pub fn find_duplicate_subtrees(root: option<rc<refcell<treenode>>>) -> vec<option<rc<refcell<treenode>>>> { let mut res = vec::new(); fn dfs(root: &option<rc<refcell<treenode>>>, sub_flag: &mut hashmap<string, i32>, flag_cnt: &mut hashmap<i32, i32>, res: &mut vec<option<rc<refcell<treenode>>>>, flag: &mut i32) -> i32 { if root.is_none() { return 0; } let (lflag, rflag) = (dfs(&root.as_ref().unwrap().borrow().left, sub_flag, flag_cnt, res, flag), dfs(&root.as_ref().unwrap().borrow().right, sub_flag, flag_cnt, res, flag)); let sub = format!("{}{}{}", root.as_ref().unwrap().borrow().val, lflag, rflag); if sub_flag.contains_key(&sub) { // 已统计过 let key = sub_flag[&sub]; let cnt = flag_cnt[&key] + 1; flag_cnt.insert(key, cnt); if cnt == 2 { // ==保证统计所有且只记录一次 res.push(root.clone()); } key } else { // 首次出现 *flag += 1; sub_flag.insert(sub, *flag); flag_cnt.insert(*flag, 1); *flag } } dfs(&root, &mut hashmap::new(), &mut hashmap::new(), &mut res, &mut 0); res } }
- 时间复杂度:o(n)
- 空间复杂度:o(n)
总结
两种方法本质上都是基于哈希表,记录重复的子树结构并统计个数,在超过111时进行记录,不过思路二更巧妙地将冗长的字符串变为常数级的标识符。
以上就是java c++ 算法题解leetcode652寻找重复子树的详细内容,更多关于java c++ 寻找重复子树的资料请关注其它相关文章!