# 输入两颗二叉树A，B，判断B是不是A的子结构

``````<span style="font-size:18px;">public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null&&root2 != null)return false;
if(root2 == null)return false;
boolean flag = false;
if(root1 != null&&root2 != null){
if(root1.val == root2.val){
flag = IsSubtree(root1,root2);
}
if(!flag){
flag = HasSubtree(root1.left,root2);
}
if(!flag){
flag = HasSubtree(root1.right,root2);
}
}
return flag;
}
public boolean IsSubtree(TreeNode root1,TreeNode root2){
if(root1 == null&&root2 != null)return false;
if(root2 == null)return true;
if(root1.val != root2.val)return false;
return IsSubtree(root1.left,root2.left)&&IsSubtree(root1.right,root2.right);
}
}</span>``````

``````public class IdenticalTree {
public boolean chkIdentical(TreeNode A, TreeNode B) {
// write code here
public boolean chkIdentical(TreeNode A, TreeNode B) {
// write code here
String str1=treeToStr(A);
String str2=treeToStr(B);

int res=getIndexOf(str1,str2);

if(res==-1)
{
return false;
}else{
return true;
}
}

public String treeToStr(TreeNode tree)
{
if(tree==null)
{
return "#";
}

StringBuilder sb=new StringBuilder();
sb.append(tree.val);
sb.append(treeToStr(tree.left));
sb.append(treeToStr(tree.right));
return sb.toString();
}

public int getIndexOf(String s1,String s2)
{
if(s1==null||s2==null||s1.equals("")||s2.equals(""))
{
return -1;
}

int[] next=getNext(s2);

char[] sc1=s1.toCharArray();
char[] sc2=s2.toCharArray();

int m1=0;
int m2=0;

while(m1<sc1.length&&m2<sc2.length)
{
if(sc1[m1]==sc2[m2])
{
m1++;
m2++;
}else if(next[m2]==-1)
{
m1++;
}else{
m2=next[m2];
}
}

return m2==sc2.length?m1-m2:-1;
}

public int[] getNext(String str)
{
int[] next=new int[str.length()];
char[] s=str.toCharArray();
next[0]=-1;
next[1]=0;

if(s.length<2)
{
return next;
}

int cur=2;
int cn=0;
while(cur<s.length)
{
if(s[cur-1]==s[cn])
{
next[cur++]=++cn;
}else if(cn>0)
{
cn=next[cn];
}else{
next[cur++]=0;
}
}
return next;

}
}
}``````
原文作者：B树
原文地址: https://blog.csdn.net/sinat_28108651/article/details/51758793
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。