572. 另一棵树的子树

给你两棵二叉树 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);
    }
}

  

 

572. 另一棵树的子树

上一篇:01ReentrantLock


下一篇:CENTOS7开机自启动脚本