Skip to content

Commit c277329

Browse files
fishercoder1534fishercoder1534
committed
add 652
1 parent 55cab6b commit c277329

File tree

3 files changed

+197
-0
lines changed

3 files changed

+197
-0
lines changed

‎README.md

+1
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

‎src/main/java/com/fishercoder/solutions/_652.java

+130
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
5+
import java.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+
public class _652 {
32+
33+
/**credit: https://discuss.leetcode.com/topic/97584/java-concise-postorder-traversal-solution*/
34+
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
35+
List<TreeNode> res = new LinkedList<>();
36+
postorder(root, new HashMap<>(), res);
37+
return res;
38+
}
39+
40+
private String postorder(TreeNode curr, HashMap<String, Integer> map, List<TreeNode> res) {
41+
if (curr == null) return "#";
42+
String serial = 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+
return serial;
48+
}
49+
50+
51+
public class MyOriginalSolution {
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+
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
61+
List<TreeNode> result = new ArrayList<>();
62+
if (root == null) return result;
63+
Map<TreeNode, List<TreeNode>> map = new HashMap<>();
64+
Queue<TreeNode> oldQueue = new LinkedList<>();
65+
Queue<TreeNode> newQueue = new LinkedList<>();
66+
oldQueue.offer(root);
67+
while (!oldQueue.isEmpty()) {
68+
int size = oldQueue.size();
69+
for (int i = 0; i < size; i++) {
70+
TreeNode curr = 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, new ArrayList<>());
80+
}
81+
}
82+
}
83+
for (TreeNode treeNode : newQueue) {
84+
findDuplicateSubtrees(treeNode, newQueue, map);
85+
}
86+
oldQueue = newQueue;
87+
}
88+
Set<TreeNode> set = new HashSet<>();
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+
return result;
96+
}
97+
98+
private void findDuplicateSubtrees(TreeNode treeNode, Queue<TreeNode> newQueue, Map<TreeNode, List<TreeNode>> map) {
99+
for (TreeNode tn : newQueue) {
100+
if (treeNode != tn) {
101+
if (isSubtree(tn, treeNode)) {
102+
List<TreeNode> list = map.getOrDefault(treeNode, new ArrayList<>());
103+
list.add(tn);
104+
map.put(treeNode, list);
105+
return;
106+
}
107+
}
108+
}
109+
}
110+
111+
private boolean isSubtree(TreeNode s, TreeNode t) {
112+
if (s == null && t == null) return true;
113+
boolean isSubTree = false;
114+
if (s != null && t != null && s.val == t.val) isSubTree = isSameTree(s, t);
115+
if (isSubTree) return true;
116+
boolean isSubTreeLeft = false;
117+
if (s.left != null) isSubTreeLeft = isSubtree(s.left, t);
118+
if (isSubTreeLeft) return true;
119+
boolean isSubTreeRight = false;
120+
if (s.right != null) isSubTreeRight = isSubtree(s.right, t);
121+
if (isSubTreeRight) return true;
122+
return false;
123+
}
124+
125+
private boolean isSameTree(TreeNode p, TreeNode q) {
126+
if (p == null || q == null) return p == q;
127+
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
128+
}
129+
}
130+
}

‎src/test/java/com/fishercoder/_652Test.java

+66
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.solutions._652;
5+
import org.junit.Before;
6+
import org.junit.BeforeClass;
7+
import org.junit.Test;
8+
9+
import java.util.ArrayList;
10+
import java.util.Arrays;
11+
import java.util.List;
12+
13+
import static org.junit.Assert.assertEquals;
14+
15+
/**
16+
* Created by stevesun on 7/30/17.
17+
*/
18+
public class _652Test {
19+
private static _652 test;
20+
private static List<TreeNode> expected;
21+
private static TreeNode root;
22+
23+
@BeforeClass
24+
public static void setup(){
25+
test = new _652();
26+
}
27+
28+
@Before
29+
public void setUp(){
30+
root = null;
31+
}
32+
33+
@Test
34+
public void test1(){
35+
root = new TreeNode(1);
36+
root.left = new TreeNode(2);
37+
root.left.left = new TreeNode(4);
38+
root.right = new TreeNode(3);
39+
root.right.left = new TreeNode(2);
40+
root.right.left.left = new TreeNode(4);
41+
root.right.right = new TreeNode(4);
42+
43+
TreeNode _2 = new TreeNode(2);
44+
_2.left = new TreeNode(4);
45+
TreeNode _4 = new TreeNode(4);
46+
expected = new ArrayList<>(Arrays.asList(_4, _2));
47+
assertEquals(expected, test.findDuplicateSubtrees(root));
48+
}
49+
50+
@Test
51+
public void test2(){
52+
expected = new ArrayList<>();
53+
assertEquals(expected, test.findDuplicateSubtrees(root));
54+
}
55+
56+
@Test
57+
public void test3(){
58+
root = new TreeNode(2);
59+
root.left = new TreeNode(1);
60+
root.right = new TreeNode(1);
61+
62+
TreeNode _1 = new TreeNode(1);
63+
expected = new ArrayList<>(Arrays.asList(_1));
64+
assertEquals(expected, test.findDuplicateSubtrees(root));
65+
}
66+
}

0 commit comments

Comments
 (0)