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

文章目录

• • 1. 暴力求解，深度优先
  • 2. KMP���法进行串匹配

    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 sOrder = new ArrayList();//用来保存s树的遍历结果，主串    List tOrder = new ArrayList();//保存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 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  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  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;    }}