FindDuplicateSubtrees [source code]
public class FindDuplicateSubtrees {
static
/****************************************************************************/
class Solution {
Map<String, List<TreeNode>> groups;
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
groups = new HashMap<> ();
inOrder (root);
List<TreeNode> res = new ArrayList<> ();
for (String ser : groups.keySet ()) {
List<TreeNode> ls = groups.get (ser);
if (ls.size () > 1)
res.add (ls.get (0));
}
return res;
}
String inOrder (TreeNode node) {
if (node == null)
return "()";
StringBuilder sb = new StringBuilder ();
sb.append ("(");
String left = inOrder (node.left);
sb.append (left);
sb.append (node.val);
String right = inOrder (node.right);
sb.append (right);
sb.append (")");
String res = sb.toString ();
groups.computeIfAbsent (res, s -> new ArrayList<> ()).add (node);
return res;
}
}
/****************************************************************************/
public static void main(String[] args) {
FindDuplicateSubtrees.Solution tester = new FindDuplicateSubtrees.Solution();
}
}
什么情况, 题目有点看不懂?
这例子给的这两个哪里是duplicate了啊?
哦, 我知道了, 是返回一个相当于每一组duplicate的代表;
比如这里, 就是红色和紫色对应的这个就是都是duplicate;
试了一下OJ, 要返回的是这个答案: [[2,4],[4]]. 当然, 你要返回的是tree, 不是TreeNode;
不小心瞄了一眼discuss, 好像这题是用serialization来写的可能性比较大, 加上tag里面给的相似题, 感觉应该是这个无误了;
same strucutre and values, 这个直接一个returned recursion应该就能解决; 这个题目难以处理的地方在于, 就算是用这个方法判断是identical的两个subtree, 你怎么把他们group到一起去?
好像除了用serialization来做hash, 没有什么其他特别好的点子了;
刚开始要想写的时候有很多想法, 比如是不是用StringBuilder比用string要好啊, 我们最后这个string=treenode的Map, value存的什么比较好啊? 有没有必要存一个完整的list啊, 能不能少存一点啊?
这些都属于Premature Optmization的范畴了; 一开始, 你一行代码都还没有的时候, 你先写出来一个能跑的代码; 然后后面你优化空间(比如Map的value少存一点), 或者优化时间(优化string操作的代价), 都是后面的事情, 一开始不要浪费时间在这个上面纠结;
随手写写然后居然就AC了, 速度是122(4), 看来string操作还是有点讲究在里面的;
具体实现的想法反正就是, 善用CLRS上面讲过的那个括号思路. 注意一下Null的处理, 返回一个(), 而不是直接返回一个空string比较好; 自己想想为什么;
editorial
Approach #1: Depth-First Search [Accepted]
Intuition
We can serialize each subtree. For example, the tree
1 / \ 2 3 / \ 4 5can be represented as the serialization 1,2,#,#,3,4,#,#,5,#,#, which is a unique representation of the tree.
核心难度就是给一个tree一个唯一ID; 用serialization来做, 也是最自然的做法; 他这里好像是一个PreOrder的结构, 然后用##来分割两个child; 这个怎么证明唯一? 感觉有点麻烦, 不如我的括号的方法更简单;
Algorithm
Perform a depth-first search, where the recursive function returns the serialization of the tree. At each node, record the result in a map, and analyze the map after to determine duplicate subtrees.
class Solution {
Map<String, Integer> count;
List<TreeNode> ans;
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
count = new HashMap();
ans = new ArrayList();
collect(root);
return ans;
}
public String collect(TreeNode node) {
if (node == null) return "#";
String serial = node.val + "," + collect(node.left) + "," + collect(node.right);
count.put(serial, count.getOrDefault(serial, 0) + 1);
if (count.get(serial) == 2)
ans.add(node);
return serial;
}
}
还是很舒服的使用全局变量, 不要有什么负罪感;
他这个方法比我写的两个地方, 一个是他ans直接也扔到全局, 然后DFS的时候直接同时更新, 省了最后一个单独的pass走Map;
另外一个就是这个:
count.put(serial, count.getOrDefault(serial, 0) + 1);
if (count.get(serial) == 2)
ans.add(node);
这个我是没有想到, 这个其实也是类似以前NLP的时候有一个作业, 判断什么singleton的时候的那个思路; 当时其实总结的还是挺好的, 这一题就没有想到用; 具体的方法就是你还是正常的在Map里面++或者--操作, 但是要特别关注0->1和1->0这两个过程;
当然, 对应到这一题, 是特别关注1->2这个过程, 一旦发生, 说明有duplicate, 可以扔到ans里面去;
另外他的Map里面存的可不是一个list of treenodes, 而是直接一个count; 这个我当时自己想的时候大概都想到了, 但是当时否决掉, 是因为觉得, 如果只存一个count, 你最后怎么返回any of these treenodes呢? 他这里就是用一个global mutation of ans来解决了这个问题: 当你检测到++ to 2的时候, 你当时就在这个node, 直接add进去就行了;
而且因为是只在判断1->2的这个瞬间, 而不是其他的比如count > 2这样的时候去add, 所以最后ans里面不可能有重复;
awice小细节还是很多的;
复杂度分析, 时间复杂度分析有点嚼头; 他这里讲的比较松散, 实际上是这样一个思路; 一开始不是不知道怎么分析吗, 就假设tree是balanced的情况;
不用去考虑tree本身, 因为我们最后关心的就是string操作带来的cost, 所以就直接看serialization就行了; 假设是balanced, 那么每一个level都是一个二分, 这里这个case很容易看出来是NlgN的复杂度;
但是这个情况实际上是BestCase; 如果是worst case, 我们最后实际上是可能depth有N的: 每一个level是左边1, 右边N-1这样分就行了;
这样一个worst case就很正常的复杂度就是N^2了;
Approach #2: Unique Identifier [Accepted]
Intuition
Suppose we have a unique identifier for subtrees: two subtrees are the same if and only if they have the same id.
Then, for a node with left child id of x and right child id of y, (node.val, x, y) uniquely determines the tree.
Algorithm
If we have seen the triple (node.val, x, y) before, we can use the identifier we've remembered. Otherwise, we'll create a new one.
大概能够理解这个意思: 在DFS的Bottom-Up的过程中, 我们实际上是从小tree到大tree这样, 不停的见到不同的subtree;
上面一种做法的问题在于, 所有的小tree的完整的serialization我们全都上层的parent全盘接收. 这个其实是很浪费的; 因为你深层分析这题为什么复杂度控制不住, 就是因为对于每一个node, 这一层的复杂度完全右两个child返回上来的string有多长给决定了;
这里直接就是用一个类似memo的操作: child返回上来的是一个ID, 而不是完整的一个长string, 因为string操作而导致的复杂度blow-up就控制住了;
class Solution {
int t;
Map<String, Integer> trees;
Map<Integer, Integer> count;
List<TreeNode> ans;
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
t = 1;
trees = new HashMap();
count = new HashMap();
ans = new ArrayList();
lookup(root);
return ans;
}
public int lookup(TreeNode node) {
if (node == null) return 0;
String serial = node.val + "," + lookup(node.left) + "," + lookup(node.right);
int uid = trees.computeIfAbsent(serial, x-> t++);
count.put(uid, count.getOrDefault(uid, 0) + 1);
if (count.get(uid) == 2)
ans.add(node);
return uid;
}
}
还是强调一个, 读代码的时候不要慌, 比如读awice这种, 几乎一点都不告诉你每一个变量的定义是什么的代码, 是比较烦人, 但是有时候是难免的; 这种时候, 你看到一个变量声明, 比如trees之后, 自己脑子里面提醒一下自己, 这个是一个string=integer的Map就行了; 看到后面每次碰到这个变量的时候, 也提醒一下自己这个信息;
一般只要不是算法写的太坑人, 这样对于理解算法已经有很大的帮助了; 我主要还是记忆力比较差, 要记得用这样那样的这种小技巧来帮助自己维护记忆力;
核心结构好像都是差不多, 多了几个全局变量而已;
trees.computeIfAbsent(serial, x-> t++);这个有点意思啊, 没想到computeIfAbsent还可以这样用的;
不对啊, 这个有什么用啊? 这个又不会修改trees, 是吧, 直接改成if trees not contains serial then t++也一样吧? 他这里主要是用的computeIfAbsent而不是putIfAbsent;
诶, 会运行诶?
java> Map<Integer, Integer> map = new HashMap<> ()
java.util.Map<java.lang.Integer, java.lang.Integer> map = {}
java> int t = 0;
int t = 0
java> map.putIfAbsent (1, t++)
java.lang.Object res2 = null
java> t
java.lang.Integer t = 1
java> map
java.util.Map<java.lang.Integer, java.lang.Integer> map = {1=0}
java> map.computeIfAbsent (1, s -> t++)
java.lang.Integer res3 = 0
java> t
java.lang.Integer t = 1
java> map
java.util.Map<java.lang.Integer, java.lang.Integer> map = {1=0}
java> map.computeIfAbsent (2, s -> t++)
java.lang.Integer res4 = 1
java> t
java.lang.Integer t = 2
java> map
java.util.Map<java.lang.Integer, java.lang.Integer> map = {1=0, 2=1}
这个是为什么啊?
哦我知道了, computeIfAbsent的这个第二个参数, 这个lambda, 实际上对应的不是一个lambda! 而是一个put操作, 只不过看起来是类似一个lambda; 一定程度上你也可以理解为是一个lambda, 但是实际上本质上是一个put操作: left -> right的意思就是put (left, right)这个意思;
算法看完感觉好像不是特别复杂? trees基本就是一个tokenization或者说memo类似的操作; 然后count还是之前的做法, 只不过现在是一个int=int的结构了;
基本思路就是在Bottom-Up的过程中, subtree从小到大, 然后我们每次拿到一个小tree, 立刻token到一个int, 丢给自己的parent, parent做出来一个string之后, 也token, 依次类推; 整个过程其实有点像在serialization空间也建立了一个tree;
这个过程是需要一个PostOrder的, 虽然他写的代码实际上看起来是PreOrder, 但是你仔细想, 其实我觉得用PostOrder来理解更合适: 在这个题目的语境下, 两种order的代码几乎是等价的;
可以参考一下这个图:
红色的对应的就是serialization空间的这个tree;
你可能有一个担心的地方, 你看, 你token的这些int, 是不是跟node.val本身的这些int是有重复的啊? 这个其实没有关系, 一个比如(a, b, c)这样的serialization, 其实implicit的, 我们知道a肯定是一个node.val空间的, 然后b和c肯定是serialization token空间的, 位置决定不可能重叠; a决定root是什么, b和c唯一决定左右的两个child, 不会有重叠的情况;
复杂度也不难分析, 现在每一个level的复杂度控制在了O(1), 所以最后最坏的就是一个O(N)就行了;
UNFINISHED
Problem Description
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.
Difficulty:Medium
Total Accepted:14.1K
Total Submissions:38.2K
Contributor:Stomach_ache
Companies
google
Related Topics
tree
Similar Questions
Serialize and Deserialize Binary TreeSerialize and Deserialize BST