Find Duplicate Subtrees
2024-09-05 12:49:56
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 listn.
分析：把每个node当成root，然后得到它的preorder traversal string, 因为子node的preorder traversal string是可以被用在parent上的，这样时间复杂度只是O(n).
class Solution {
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
List<TreeNode> res = new LinkedList<>();
preorder(root, new HashMap<>(), res);
return res;
}
public String preorder(TreeNode cur, Map<String, Integer> map, List<TreeNode> res) {
if (cur == null) return "#";
String serial = cur.val + "," + preorder(cur.left, map, res) + "," + preorder(cur.right, map, res);
if (map.getOrDefault(serial, ) == ) res.add(cur);
map.put(serial, map.getOrDefault(serial, ) + );
return serial;
}
}
最新文章
- [python]初试页面抓取——抓取沪深股市交易龙虎榜数据
- JQUERY操作css与css()方法、获取设置尺寸；
- Spring常用的接口和类（三）
- CC2540开发板学习笔记（四）——定时器
- EXTJS 3.0 资料 控件之 GridPanel属性与方法大全
- uvalive 4728 Squares
- free 堡垒机
- ERROR<53761> - Plugins - conn=-1 op=-1 msgId=-1 - Connection Bind through PTA failed (91). Retrying...
- 透明窗口（窗口上面文字图片等内容不透明）的实现（使用SetLayeredWindowAttributes API函数）
- SQL Server Profiler追踪数据库死锁
- React Fiber 数据结构揭秘
- 8.1 GOF 设计模式：关于设计模式
- Nevertheless 和 Nonetheless，你用对了吗？
- react-redux单元测试(基于react-addons-test-utils,mocha）
- C# 函数式编程：LINQ
- 前端开发---HTML---介绍
- MVC ---- 去掉HTML过滤
- Django MySQL数据库操作
- 北京Uber优步司机奖励政策（4月16日）
- DelegatingFilterProxy干了什么？