自学内容网 自学内容网

java数据结构与算法刷题-----LeetCode572. 另一棵树的子树(经典题,树字符串化KMP)

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

在这里插入图片描述

1. 暴力求解,深度优先

解题思路:时间复杂度O(s*t)其中s是树的结点个数,t是子树的结点个数。空间复杂度O(max(ds,dt))其中ds是树的深度,dt是子树的深度
  1. 我们先对整个树深度优先遍历
  2. 每个结点都与子树的根节点进行比对
  3. 如果对上了,就以当前结点为根节点,进行和子树的深度优先遍历,看看是否一一对应
  4. 对应上就返回true,没对应上就继续深度优先遍历。直到整个树遍历完成
代码

在这里插入图片描述

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null && subRoot == null) return true;//如果都为null,就无需找子树了
        else if(root == null || subRoot == null) return false;//如果有一个为null,另一个不是null,肯定不是子树
        //先进行深度优先遍历,直接比对当前结点,如果能对上就可以省下很多时间
        //遍历到底时,再去isSameTree方法中,判断以当前root为根的子树,是否和subRoot是一样的
        else 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 isSameTree(root.left,subRoot.left) && isSameTree(root.right,subRoot.right);
        }
        return false;
    }
}

2. KMP算法进行串匹配

KMP算法https://blog.csdn.net/grd_java/article/details/136107363
解题思路:时间复杂度O(s+t),空间复杂度O(s+t)
  1. 生成两颗树的遍历序列,以类似如下的形式:(下面形式是广度(层序)遍历序列,需要额外空间辅助,所以我们放弃)
    在这里插入图片描述
  2. 为了效率和更少的空间,我们使用广度优先遍历。那么就需要两个不同的值,来表示某结点左子树为空,和右子树为空的情况。
  3. 同样为了效率,我们不使用字符串比较,选用int型容器,比如int型的链表来生成匹配串
  4. 那么null如何来表示呢?
  1. 我们可以规定两个值,来分别表示左子树为null和右子树为null的情况
  2. 这里我选择先找到树中最大值max,然后令max+1表示左子树为空情况,max+2表示右子树为空情况
  1. 生成两颗树的匹配串后,让大树作为主字符串,要匹配的子树作为要匹配的子串,改编KMP算法,如果匹配成功,说明树中可以匹配到子树
代码:leetcode的特色之一就是,更优的算法,有时因为使用程序自带的特殊容器(比如Java中的List),因为这些容器初始化比较耗时间,反而耗时更高。但是实际工作场景,一旦数据量起来,肯定是这个算法优于上面的暴力解法的。

在这里插入图片描述

class Solution {
    List<Integer> sOrder = new ArrayList<Integer>();//用来保存s树的遍历结果,主串
    List<Integer> tOrder = new ArrayList<Integer>();//保存t树,匹配串
    
    int maxElement, lNull, rNull;//maxElement保存两颗树中最大值,lNull为左子树为空的标记,rNull为右子树为空
    //此方法获取树中最大值,深度优先
    public void getMaxElement(TreeNode t) {
        if (t == null) return;
        maxElement = Math.max(maxElement, t.val);
        getMaxElement(t.left);
        getMaxElement(t.right);
    }
    //此方法生成树的遍历字符串,其中,左右子树为null的,使用lNull和rNull填充
    public void getDfsOrder(TreeNode t, List<Integer> tar) {
        if (t == null) return;
        
        tar.add(t.val);//填充当前值
        //如果左子树为null填充lNull,否则继续遍历左子树
        if (t.left != null) getDfsOrder(t.left, tar);
        else tar.add(lNull);
        //右子树不为null继续遍历右子树,否则填充rNull
        if (t.right != null) getDfsOrder(t.right, tar);
        else tar.add(rNull);
    }
    //入口方法,1.获取树最大值max,并令max+1作为lNull,max+2作为rNull
    //2. 获取两颗树的遍历串。 3. kmp算法进行匹配
    public boolean isSubtree(TreeNode s, TreeNode t) {
        maxElement = Integer.MIN_VALUE;
        //获取两颗树中的最大值
        getMaxElement(s);
        getMaxElement(t);
        //则最大值+1和+2是树中绝对不存在的两个值
        lNull = maxElement + 1;//最大值+1作为左子树为空的填充串
        rNull = maxElement + 2;//最大值+2为右子树为空
        //获取两颗树的遍历串
        getDfsOrder(s, sOrder);
        getDfsOrder(t, tOrder);
        //通过kmp算法
        return kmp();
    }
    //kmp算法,如果匹配到子串,说明树中可以匹配到t这颗子树
    public boolean kmp() {
        int sLen = sOrder.size(), tLen = tOrder.size();
        int[] fail = new int[tOrder.size()];
        fail[0] = 0;
        for (int i = 1, j = 0; i < tLen; ++i) {
            while (j > 0 && !(tOrder.get(i).equals(tOrder.get(j)))) j = fail[j-1];
            if (tOrder.get(i).equals(tOrder.get(j))) ++j;
            fail[i] = j;
        }
        for (int i = 0, j = 0; i < sLen; ++i) {
            while (j > 0 && !(sOrder.get(i).equals(tOrder.get(j)))) j = fail[j-1];
            if (sOrder.get(i).equals(tOrder.get(j))) ++j;
            if (j == tLen) return true;
        }
        return false;
    }
}


原文地址:https://blog.csdn.net/grd_java/article/details/136403984

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!