public class a18_IsSubTree {
public static boolean hasSubTree(TreeNode treeRoot1, TreeNode treeRoot2) {
boolean result = false;
if (treeRoot1 != null && treeRoot2 != null) {
if (treeRoot1.data == treeRoot2.data) {
result = DoesTree1HasTree2(treeRoot1, treeRoot2);
}
if (!result) {
result = hasSubTree(treeRoot1.left, treeRoot2);
}
if (!result)
result = hasSubTree(treeRoot1.right, treeRoot2);
}
return result;
}
private static boolean DoesTree1HasTree2(TreeNode treeRoot1, TreeNode treeRoot2) {
if (treeRoot2 == null)
return true;
if (treeRoot1 == null)
return false;
if (treeRoot1.data != treeRoot2.data) {
return false;
}
return DoesTree1HasTree2(treeRoot1.left, treeRoot2.left) && DoesTree1HasTree2(treeRoot1.right, treeRoot2.right);
}
public static void main(String[] args) {
TreeNode tree1 = new TreeNode(1);
TreeNode tree2 = new TreeNode(2);
TreeNode tree3 = new TreeNode(3);
TreeNode tree4 = new TreeNode(4);
TreeNode tree5 = new TreeNode(5);
TreeNode tree6 = new TreeNode(6);
TreeNode tree7 = new TreeNode(7);
TreeNode tree8 = new TreeNode(8);
tree1.left = tree2;
tree1.right = tree3;
tree2.left = tree4;
tree2.right = tree5;
tree3.left = tree6;
tree3.right = tree7;
tree4.left = tree8;
TreeNode tree11 = new TreeNode(2);
TreeNode tree22 = new TreeNode(4);
TreeNode tree33 = new TreeNode(8);
tree11.left = tree22;
tree22.left = tree33;
System.out.println(hasSubTree(tree1, tree11));
}
}
class TreeNode {
int data;
TreeNode left = null;
TreeNode right = null;
TreeNode(int data) {
this.data = data;
}
}