给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
解法一:先序列化再用kmp
class Solution { public boolean isSubtree(TreeNode root, TreeNode subRoot) { List<String> list1=new ArrayList<>(); List<String> list2=new ArrayList<>(); preSerial(root,list1); preSerial(subRoot,list2); return getIndexOf(list1,list2)!=-1; } public int getIndexOf(List<String> list1,List<String> list2){ if(list1==null||list2==null||list1.size()<list2.size()){ return -1; } int[] nexts=getNextArray(list2); int x=0; int y=0; while(list1.size()>x && list2.size()>y){ if(list1.get(x).equals(list2.get(y))){ x++; y++; }else if(nexts[y]==-1){ x++; }else{ y=nexts[y]; } } return y==list2.size()?x-y:-1; } public int[] getNextArray(List<String> list){ if(list==null||list.size()==0){ return new int[]{-1}; } int[] nexts=new int[list.size()]; nexts[0]=-1; nexts[1]=0; int y=0; int i=2; while(i<list.size()){ if(list.get(i-1).equals(list.get(y))){ nexts[i++]=++y; }else if(y>0){ y=nexts[y]; }else{ nexts[i++]=0; } } return nexts; } public void preSerial(TreeNode node,List<String> list){ if(node==null){ list.add("#"); return; } list.add(String.valueOf(node.val)); preSerial(node.left,list); preSerial(node.right,list); } }
解法二:递归
判断是否是其子树:
1、整树相等
2、左子树相等
3、右子树相等
class Solution { public boolean isSubtree(TreeNode root, TreeNode subRoot) { if(root==null){ return false; } if(subRoot==null){ return true; } return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot)||isSameTree(root,subRoot); } public boolean isSameTree(TreeNode root,TreeNode subRoot){ if(root==null&&subRoot==null){ return true; } if(root==null|| subRoot==null){ return false; } if(root.val!=subRoot.val){ return false; } return isSameTree(root.left,subRoot.left)&&isSameTree(root.right,subRoot.right); } }