1+ package Algorithms .tree ;
2+
3+ import java .util .*;
4+
5+
6+ public class LargestCommonSubtrees {
7+ /*
8+ * Function: Find all the common subtrees root that have most number
9+ */
10+ private static class TreeNode {
11+ int val ;
12+ ArrayList <TreeNode >subNodes ;
13+ public TreeNode (int val ,ArrayList <TreeNode >subNodes ) {
14+ this .val =val ;
15+ this .subNodes =subNodes ;
16+ }
17+ }
18+
19+ public static void main (String []args ) {
20+ /*
21+ * 1
22+ *
23+ * / \ \
24+ * 2 3 4
25+ * / \ / \
26+ * 5 6 8 9
27+ * \ \
28+ * 7 10
29+ * */
30+ TreeNode r1 =new TreeNode (1 ,new ArrayList <TreeNode >());
31+ TreeNode r2 =new TreeNode (2 ,new ArrayList <TreeNode >());
32+ TreeNode r3 =new TreeNode (3 ,new ArrayList <TreeNode >());
33+ TreeNode r4 =new TreeNode (4 ,new ArrayList <TreeNode >());
34+ TreeNode r5 =new TreeNode (5 ,new ArrayList <TreeNode >());
35+ TreeNode r6 =new TreeNode (6 ,new ArrayList <TreeNode >());
36+ TreeNode r7 =new TreeNode (7 ,new ArrayList <TreeNode >());
37+ TreeNode r8 =new TreeNode (8 ,new ArrayList <TreeNode >());
38+ TreeNode r9 =new TreeNode (9 ,new ArrayList <TreeNode >());
39+ TreeNode r10 =new TreeNode (10 ,new ArrayList <TreeNode >());
40+
41+ r1 .subNodes .add (r2 );
42+ r1 .subNodes .add (r3 );
43+ r1 .subNodes .add (r4 );
44+
45+ r2 .subNodes .add (r5 );
46+ r2 .subNodes .add (r6 );
47+
48+ r6 .subNodes .add (r7 );
49+
50+ r4 .subNodes .add (r8 );
51+ r4 .subNodes .add (r9 );
52+
53+ r9 .subNodes .add (r10 );
54+
55+ ArrayList <ArrayList <TreeNode >>ret =largestCommonSubtrees (r1 );
56+ for (ArrayList <TreeNode >arrayl :ret ) {
57+ for (TreeNode t :arrayl ) {
58+ System .out .println (t .val );
59+ }
60+ }
61+
62+ }
63+
64+ public static ArrayList <ArrayList <TreeNode >>largestCommonSubtrees (TreeNode root ) {
65+ if (root ==null ) {
66+ return null ;
67+ }
68+
69+ ArrayList <ArrayList <TreeNode >>ret =new ArrayList <ArrayList <TreeNode >>();
70+
71+ // store all the tree nodes to a arrayList.
72+ ArrayList <TreeNode >nodes =new ArrayList <TreeNode >();
73+ traversalTree (root ,nodes );
74+
75+ int maxNum =0 ;
76+
77+ HashMap <Integer ,Integer >hash =new HashMap <Integer ,Integer >();
78+
79+ TreeNode r1 =null ;
80+ TreeNode r2 =null ;
81+
82+
83+ // compare all the nodes.
84+ int size =nodes .size ();
85+ for (int i =0 ;i <size ;i ++) {
86+ for (int j =0 ;j <size ;j ++) {
87+ if (i ==j ) {
88+ continue ;
89+ }
90+ int num =compareTree (nodes .get (i ),nodes .get (j ),hash );
91+ if (num >maxNum ) {
92+ ArrayList <TreeNode >iden =new ArrayList <TreeNode >();
93+ iden .add (nodes .get (i ));
94+ iden .add (nodes .get (j ));
95+
96+ ret .add (iden );
97+ r1 =nodes .get (i );
98+ r2 =nodes .get (j );
99+ }
100+ }
101+ }
102+
103+ ArrayList <ArrayList <TreeNode >>retNew =new ArrayList <ArrayList <TreeNode >>();
104+ retNew .add (new ArrayList <TreeNode >());
105+ retNew .get (0 ).add (r1 );
106+ retNew .get (0 ).add (r2 );
107+ return retNew ;
108+ }
109+
110+
111+ // compare two tree, if same, return the number of leafs. if no, return -1;
112+ public static int compareTree (TreeNode r1 ,TreeNode r2 ,HashMap <Integer ,Integer >hash ) {
113+ if (r1 ==null &&r2 ==null ) {
114+ return 0 ;
115+ }
116+
117+ if (r1 ==null ||r2 ==null ) {
118+ return -1 ;
119+ }
120+
121+ // the number of subtrees should be same.
122+ if (r1 .subNodes .size () !=r2 .subNodes .size ()) {
123+ return -1 ;
124+ }
125+
126+ int num =1 ;// the root itself.
127+
128+ for (int i =0 ;i <r1 .subNodes .size ();i ++) {
129+ // get the subNode of r1.
130+ TreeNode subNode1 =r1 .subNodes .get (i );
131+ TreeNode subNode2 =r2 .subNodes .get (i );
132+
133+ int HashCode =hashCode (subNode1 ,subNode2 );
134+
135+ Integer numNode =hash .get (HashCode );
136+ if (numNode ==null ) {
137+ numNode =compareTree (subNode1 ,subNode2 ,hash );
138+ }
139+
140+ if (numNode == -1 ) {
141+ // not the same, should return;
142+ num = -1 ;
143+ break ;
144+ }else {
145+ num +=numNode ;
146+ continue ;
147+ }
148+ }
149+
150+ int hashCodeRoot =hashCode (r1 ,r2 );
151+ hash .put (hashCodeRoot ,num );
152+
153+ return num ;
154+ }
155+
156+ public static int hashCode (TreeNode r1 ,TreeNode r2 ) {
157+ int hash =r1 .hashCode () *31 +r2 .hashCode ();
158+ return hash ;
159+ }
160+
161+ public static void traversalTree (TreeNode root ,ArrayList <TreeNode >ret ) {
162+ if (root ==null ) {
163+ return ;
164+ }
165+
166+ ret .add (root );
167+
168+ // add all the sub nodes.
169+ if (root .subNodes !=null ) {
170+ for (TreeNode t :root .subNodes ) {
171+ traversalTree (t ,ret );
172+ }
173+ }
174+ }
175+
176+
177+ }