package jianzhioffer;
import java.util.Scanner;
/**
* 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
* 采用两种方法：递归判断节点；对两个树进行先序遍历/DFS.对序列采用KMP算法，判断是否为子序列
*/
//树节点类
/*class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Solution16 {
//方法一：递归进行节点的判断
public static boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result = false; //标志位，判断是否匹配成功
//当tree1和Tree2都不为零的时候，才进行比较，否则直接返回false
if(root1 != null && root2 != null){
//如果找到了对应的tree2的根节点的点
if(root1.val == root2.val){
//以这个根节点为起点判断是否包含Tree2
result = Tree1hasTree2(root1,root2) ;
}
//如果找不到，那么就再去root1的左儿子当作起点，去判断是否包含tree2
if(!result){
result = HasSubtree(root1.left,root2);
}
//如果找不到，那么就再去root的右儿子作为起点，去判断是否包含tree2
if(!result){
result = HasSubtree(root1.right,root2);
}
}
//返回结果
return result;
}
private static boolean Tree1hasTree2(TreeNode node1, TreeNode node2) {
// 如果Tree2已经遍历完了都能对应上，返回True
if(node2 == null){
return true;
}
//如果Tree2还没遍历完，Tree1却遍历完了，返回false
if(node1 == null){
return false;
}
//如果其中有一个点没有对应上，返回false
if(node1.val != node2.val){
return false;
}
//如果根节点对应上，那么分别去子节点下面匹配
return Tree1hasTree2(node1.left,node2.left) && Tree1hasTree2(node2.right,node2.right);
}
//利用KMP算法，将root1和root2分别按先序遍历序列化，运用KMP算法匹配序列化结果
/* public static boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null){
return false;
}
char[] str = Serialize(root1).toCharArray();
char[] pattern = Serialize(root2).toCharArray();
int[] next = new int[pattern.length];
System.out.println(String.valueOf(str));
System.out.println(String.valueOf(pattern));
getNext(pattern,next);
return KMP(str,pattern,next);
}
public static String Serialize(TreeNode root) {
//有点问题还没实现，需要改进
if(root == null)
return "";
StringBuffer buffer = new StringBuffer();
int i;
//删除序列尾部的$
for(i=buffer.length()-1; i>=0;i--){
if(buffer.charAt(i) == ' ' || buffer.charAt(i)=='$'){
continue;
}else{
break;
}
}
buffer.delete(i+1, buffer.length());
return buffer.toString();
}
public static void getNext(char[] pattern, int[] next) {
if(pattern == null || pattern.length ==0)
return;
int i = 0, j = -1;
next[0] = -1;
while(i<pattern.length-1){
if(j ==-1 || pattern[i] == pattern[j]){
++i; ++j;
if(pattern[i] == pattern[j]){
next[i] = next[j];
}else{
next[i] = j;
}
}else{
j = next[j];
}
}
}
public static boolean KMP(char[] str, char[] pattern, int[] next) {
if(str == null || pattern == null)
return false;
if(str.length<pattern.length)
return false;
int i = 0,j =0,len = str.length;
while(i<len && j<pattern.length ){
if(j == -1 || str[i] == pattern[j]){
i++;j++;
}else{
j = next[j];
}
}
if(j == pattern.length) //表示最后一个字符也想等，匹配成功
return true;
return false;
}
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] a1 = new int[n];
int[] a2 = new int[m];
for(int i = 0;i<n;i++){
a1[i] = sc.nextInt();
}
for(int i = 0;i<m;i++){
a2[i] = sc.nextInt();
}
TreeNode tree1 = new TreeNode(a1[0]);
TreeNode tree2 = new TreeNode(a1[1]);
TreeNode tree3 = new TreeNode(a1[2]);
TreeNode tree4 = new TreeNode(a1[3]);
TreeNode tree5 = new TreeNode(a1[4]);
tree1.left = tree2;
tree1.right = tree3;
tree2.left = tree4;
tree2.right = tree5;
TreeNode node1 = new TreeNode(a2[0]);
TreeNode node2 = new TreeNode(a2[1]);
TreeNode node3 = new TreeNode(a2[2]);
node1.left = node2;
node1.right = node3;
boolean result = HasSubtree(tree1,node1);
System.out.println(result);
}
}
