|
11 | 11 | importjava.util.Queue; |
12 | 12 | importjava.util.Set; |
13 | 13 |
|
14 | | - |
15 | 14 | /** |
16 | 15 | * 652. Find Duplicate Subtrees |
17 | 16 | * |
|
37 | 36 | Therefore, you need to return above trees' root in the form of a list. |
38 | 37 | */ |
39 | 38 | publicclass_652 { |
| 39 | +publicstaticclassSolution1 { |
40 | 40 |
|
41 | | -/**credit: https://discuss.leetcode.com/topic/97584/java-concise-postorder-traversal-solution*/ |
42 | | - |
43 | | -/**You don't actually need to check if every other tree is a duplicate of current node, |
44 | | - * just when you go through each node, you'll see whether there's already one in the map, |
45 | | - * since map.containsKey() checks this TreeNode.*/ |
46 | | -publicList<TreeNode>findDuplicateSubtrees(TreeNoderoot) { |
47 | | -List<TreeNode>res =newLinkedList<>(); |
48 | | -postorder(root,newHashMap<>(),res); |
49 | | -returnres; |
50 | | - } |
51 | | - |
52 | | -privateStringpostorder(TreeNodecurr,HashMap<String,Integer>map,List<TreeNode>res) { |
53 | | -if (curr ==null) { |
54 | | -return"#"; |
55 | | - } |
56 | | -Stringserial =curr.val +"," +postorder(curr.left,map,res) +"," +postorder(curr.right,map,res); |
57 | | -if (map.getOrDefault(serial,0) ==1) { |
58 | | -res.add(curr); |
59 | | - } |
60 | | -map.put(serial,map.getOrDefault(serial,0) +1); |
61 | | -returnserial; |
62 | | - } |
63 | | - |
64 | | - |
65 | | -publicclassMyOriginalSolution { |
66 | | -/**This solution is blocked at [2,1,1] test case and I've asked a question here: |
67 | | - * https://discuss.leetcode.com/topic/97746/oj-bug-for-test-case-2-1-1-or-somewhere-my-code-is-wrong*/ |
| 41 | +/**credit: https://discuss.leetcode.com/topic/97584/java-concise-postorder-traversal-solution*/ |
68 | 42 |
|
69 | 43 | /** |
70 | | - *Use BFS to traverse each node, at this time, put each node into Map as key (except rootnode since root won't have duplicates), |
71 | | - *then use DFS to visit all of its siblings to find possible duplite subtrees, |
72 | | - *because duplicate could only possibly be found in siblings or sibling's children. |
| 44 | + *You don't actually need to check if every other tree is a duplicate of currentnode, |
| 45 | + *just when you go through each node, you'll see whether there's already one in the map, |
| 46 | + *since map.containsKey() checks this TreeNode. |
73 | 47 | */ |
74 | 48 | publicList<TreeNode>findDuplicateSubtrees(TreeNoderoot) { |
75 | | -List<TreeNode>result =newArrayList<>(); |
76 | | -if (root ==null) { |
77 | | -returnresult; |
78 | | - } |
79 | | -Map<TreeNode,List<TreeNode>>map =newHashMap<>(); |
80 | | -Queue<TreeNode>oldQueue =newLinkedList<>(); |
81 | | -Queue<TreeNode>newQueue =newLinkedList<>(); |
82 | | -oldQueue.offer(root); |
83 | | -while (!oldQueue.isEmpty()) { |
84 | | -intsize =oldQueue.size(); |
85 | | -for (inti =0;i <size;i++) { |
86 | | -TreeNodecurr =oldQueue.poll(); |
87 | | -if (curr.left !=null) { |
88 | | -newQueue.offer(curr.left); |
89 | | - } |
90 | | -if (curr.right !=null) { |
91 | | -newQueue.offer(curr.right); |
92 | | - } |
93 | | -if (curr !=root) { |
94 | | -if (!map.containsKey(curr)) { |
95 | | -map.put(curr,newArrayList<>()); |
96 | | - } |
97 | | - } |
98 | | - } |
99 | | -for (TreeNodetreeNode :newQueue) { |
100 | | -findDuplicateSubtrees(treeNode,newQueue,map); |
101 | | - } |
102 | | -oldQueue =newQueue; |
103 | | - } |
104 | | -Set<TreeNode>set =newHashSet<>(); |
105 | | -for (Map.Entry<TreeNode,List<TreeNode>>entry :map.entrySet()) { |
106 | | -if (entry.getValue().size() >0) { |
107 | | -set.add(entry.getKey()); |
108 | | - } |
109 | | - } |
110 | | -result.addAll(set); |
111 | | -returnresult; |
| 49 | +List<TreeNode>res =newLinkedList<>(); |
| 50 | +postorder(root,newHashMap<>(),res); |
| 51 | +returnres; |
112 | 52 | } |
113 | 53 |
|
114 | | -privatevoidfindDuplicateSubtrees(TreeNodetreeNode,Queue<TreeNode>newQueue,Map<TreeNode,List<TreeNode>>map) { |
115 | | -for (TreeNodetn :newQueue) { |
116 | | -if (treeNode !=tn) { |
117 | | -if (isSubtree(tn,treeNode)) { |
118 | | -List<TreeNode>list =map.getOrDefault(treeNode,newArrayList<>()); |
119 | | -list.add(tn); |
120 | | -map.put(treeNode,list); |
121 | | -return; |
122 | | - } |
123 | | - } |
| 54 | +privateStringpostorder(TreeNodecurr,HashMap<String,Integer>map,List<TreeNode>res) { |
| 55 | +if (curr ==null) { |
| 56 | +return"#"; |
124 | 57 | } |
125 | | - } |
126 | | - |
127 | | -privatebooleanisSubtree(TreeNodes,TreeNodet) { |
128 | | -if (s ==null &&t ==null) { |
129 | | -returntrue; |
130 | | - } |
131 | | -booleanisSubTree =false; |
132 | | -if (s !=null &&t !=null &&s.val ==t.val) { |
133 | | -isSubTree =isSameTree(s,t); |
134 | | - } |
135 | | -if (isSubTree) { |
136 | | -returntrue; |
137 | | - } |
138 | | -booleanisSubTreeLeft =false; |
139 | | -if (s.left !=null) { |
140 | | -isSubTreeLeft =isSubtree(s.left,t); |
141 | | - } |
142 | | -if (isSubTreeLeft) { |
143 | | -returntrue; |
144 | | - } |
145 | | -booleanisSubTreeRight =false; |
146 | | -if (s.right !=null) { |
147 | | -isSubTreeRight =isSubtree(s.right,t); |
148 | | - } |
149 | | -if (isSubTreeRight) { |
150 | | -returntrue; |
151 | | - } |
152 | | -returnfalse; |
153 | | - } |
154 | | - |
155 | | -privatebooleanisSameTree(TreeNodep,TreeNodeq) { |
156 | | -if (p ==null ||q ==null) { |
157 | | -returnp ==q; |
| 58 | +Stringserial =curr.val +"," +postorder(curr.left,map,res) +"," +postorder(curr.right,map,res); |
| 59 | +if (map.getOrDefault(serial,0) ==1) { |
| 60 | +res.add(curr); |
158 | 61 | } |
159 | | -returnp.val ==q.val &&isSameTree(p.left,q.left) &&isSameTree(p.right,q.right); |
| 62 | +map.put(serial,map.getOrDefault(serial,0) +1); |
| 63 | +returnserial; |
160 | 64 | } |
161 | 65 | } |
162 | 66 | } |