Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc277329

Browse files
add 652
1 parent55cab6b commitc277329

File tree

3 files changed

+197
-0
lines changed

3 files changed

+197
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@ Your ideas/fixes/algorithms are more than welcome!
2020

2121
| # | Title | Solutions | Time | Space | Difficulty | Tag | Notes
2222
|-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
23+
|652|[Find Duplicate Subtrees](https://leetcode.com/problems/find-duplicate-subtrees/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_652.java) | O(n) |O(n) | Medium | Tree
2324
|651|[4 Keys Keyboard](https://leetcode.com/problems/4-keys-keyboard/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_651.java) | O(n^2) |O(n) | Medium | DP
2425
|650|[2 Keys Keyboard](https://leetcode.com/problems/2-keys-keyboard/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_650.java) | O(n^2) |O(n) | Medium | DP
2526
|648|[Replace Words](https://leetcode.com/problems/replace-words/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_648.java) | O(n) |O(n) | Medium | Trie
Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
packagecom.fishercoder.solutions;
2+
3+
importcom.fishercoder.common.classes.TreeNode;
4+
5+
importjava.util.*;
6+
7+
/**
8+
* 652. Find Duplicate Subtrees
9+
*
10+
* 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.
11+
12+
Two trees are duplicate if they have the same structure with same node values.
13+
14+
Example 1:
15+
1
16+
/ \
17+
2 3
18+
/ / \
19+
4 2 4
20+
/
21+
4
22+
The following are two duplicate subtrees:
23+
2
24+
/
25+
4
26+
and
27+
4
28+
29+
Therefore, you need to return above trees' root in the form of a list.
30+
*/
31+
publicclass_652 {
32+
33+
/**credit: https://discuss.leetcode.com/topic/97584/java-concise-postorder-traversal-solution*/
34+
publicList<TreeNode>findDuplicateSubtrees(TreeNoderoot) {
35+
List<TreeNode>res =newLinkedList<>();
36+
postorder(root,newHashMap<>(),res);
37+
returnres;
38+
}
39+
40+
privateStringpostorder(TreeNodecurr,HashMap<String,Integer>map,List<TreeNode>res) {
41+
if (curr ==null)return"#";
42+
Stringserial =curr.val +"," +postorder(curr.left,map,res) +"," +postorder(curr.right,map,res);
43+
if (map.getOrDefault(serial,0) ==1) {
44+
res.add(curr);
45+
}
46+
map.put(serial,map.getOrDefault(serial,0) +1);
47+
returnserial;
48+
}
49+
50+
51+
publicclassMyOriginalSolution {
52+
/**This solution is blocked at [2,1,1] test case and I've asked a question here:
53+
* https://discuss.leetcode.com/topic/97746/oj-bug-for-test-case-2-1-1-or-somewhere-my-code-is-wrong*/
54+
55+
/**
56+
* Use BFS to traverse each node, at this time, put each node into Map as key (except root node since root won't have duplicates),
57+
* then use DFS to visit all of its siblings to find possible duplite subtrees,
58+
* because duplicate could only possibly be found in siblings or sibling's children.
59+
*/
60+
publicList<TreeNode>findDuplicateSubtrees(TreeNoderoot) {
61+
List<TreeNode>result =newArrayList<>();
62+
if (root ==null)returnresult;
63+
Map<TreeNode,List<TreeNode>>map =newHashMap<>();
64+
Queue<TreeNode>oldQueue =newLinkedList<>();
65+
Queue<TreeNode>newQueue =newLinkedList<>();
66+
oldQueue.offer(root);
67+
while (!oldQueue.isEmpty()) {
68+
intsize =oldQueue.size();
69+
for (inti =0;i <size;i++) {
70+
TreeNodecurr =oldQueue.poll();
71+
if (curr.left !=null) {
72+
newQueue.offer(curr.left);
73+
}
74+
if (curr.right !=null) {
75+
newQueue.offer(curr.right);
76+
}
77+
if (curr !=root) {
78+
if (!map.containsKey(curr)) {
79+
map.put(curr,newArrayList<>());
80+
}
81+
}
82+
}
83+
for (TreeNodetreeNode :newQueue) {
84+
findDuplicateSubtrees(treeNode,newQueue,map);
85+
}
86+
oldQueue =newQueue;
87+
}
88+
Set<TreeNode>set =newHashSet<>();
89+
for (Map.Entry<TreeNode,List<TreeNode>>entry :map.entrySet()) {
90+
if (entry.getValue().size() >0) {
91+
set.add(entry.getKey());
92+
}
93+
}
94+
result.addAll(set);
95+
returnresult;
96+
}
97+
98+
privatevoidfindDuplicateSubtrees(TreeNodetreeNode,Queue<TreeNode>newQueue,Map<TreeNode,List<TreeNode>>map) {
99+
for (TreeNodetn :newQueue) {
100+
if (treeNode !=tn) {
101+
if (isSubtree(tn,treeNode)) {
102+
List<TreeNode>list =map.getOrDefault(treeNode,newArrayList<>());
103+
list.add(tn);
104+
map.put(treeNode,list);
105+
return;
106+
}
107+
}
108+
}
109+
}
110+
111+
privatebooleanisSubtree(TreeNodes,TreeNodet) {
112+
if (s ==null &&t ==null)returntrue;
113+
booleanisSubTree =false;
114+
if (s !=null &&t !=null &&s.val ==t.val)isSubTree =isSameTree(s,t);
115+
if (isSubTree)returntrue;
116+
booleanisSubTreeLeft =false;
117+
if (s.left !=null)isSubTreeLeft =isSubtree(s.left,t);
118+
if (isSubTreeLeft)returntrue;
119+
booleanisSubTreeRight =false;
120+
if (s.right !=null)isSubTreeRight =isSubtree(s.right,t);
121+
if (isSubTreeRight)returntrue;
122+
returnfalse;
123+
}
124+
125+
privatebooleanisSameTree(TreeNodep,TreeNodeq) {
126+
if (p ==null ||q ==null)returnp ==q;
127+
returnp.val ==q.val &&isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);
128+
}
129+
}
130+
}
Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.common.classes.TreeNode;
4+
importcom.fishercoder.solutions._652;
5+
importorg.junit.Before;
6+
importorg.junit.BeforeClass;
7+
importorg.junit.Test;
8+
9+
importjava.util.ArrayList;
10+
importjava.util.Arrays;
11+
importjava.util.List;
12+
13+
importstaticorg.junit.Assert.assertEquals;
14+
15+
/**
16+
* Created by stevesun on 7/30/17.
17+
*/
18+
publicclass_652Test {
19+
privatestatic_652test;
20+
privatestaticList<TreeNode>expected;
21+
privatestaticTreeNoderoot;
22+
23+
@BeforeClass
24+
publicstaticvoidsetup(){
25+
test =new_652();
26+
}
27+
28+
@Before
29+
publicvoidsetUp(){
30+
root =null;
31+
}
32+
33+
@Test
34+
publicvoidtest1(){
35+
root =newTreeNode(1);
36+
root.left =newTreeNode(2);
37+
root.left.left =newTreeNode(4);
38+
root.right =newTreeNode(3);
39+
root.right.left =newTreeNode(2);
40+
root.right.left.left =newTreeNode(4);
41+
root.right.right =newTreeNode(4);
42+
43+
TreeNode_2 =newTreeNode(2);
44+
_2.left =newTreeNode(4);
45+
TreeNode_4 =newTreeNode(4);
46+
expected =newArrayList<>(Arrays.asList(_4,_2));
47+
assertEquals(expected,test.findDuplicateSubtrees(root));
48+
}
49+
50+
@Test
51+
publicvoidtest2(){
52+
expected =newArrayList<>();
53+
assertEquals(expected,test.findDuplicateSubtrees(root));
54+
}
55+
56+
@Test
57+
publicvoidtest3(){
58+
root =newTreeNode(2);
59+
root.left =newTreeNode(1);
60+
root.right =newTreeNode(1);
61+
62+
TreeNode_1 =newTreeNode(1);
63+
expected =newArrayList<>(Arrays.asList(_1));
64+
assertEquals(expected,test.findDuplicateSubtrees(root));
65+
}
66+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp