【算法】【二叉树模块】求一个二叉树“子树“是否包含另一个二叉树的全部拓扑结构

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定两个二叉树根节点r1和r2，求r1是否存在包含r2的子树（不是拓扑结构）
如：
t1：

t2：

这里头结点123完全包含头结点6，因此结果为true

解决方案

首先参考一下：

https://swzhao.blog.csdn.net/article/details/127070018

方案一：
方案一就是参考中的方法，只不过改变了一些null值时的判断逻辑，其他都一样
时间O(n) 空间O(n)
方案二：
参考：

https://swzhao.blog.csdn.net/article/details/126860419

方案二原理为数的序列化后，字符串存在包含关系，正常来说java中String的contains复杂度很高为MXN
因此这里使用了KMP算法，后续KMP算法会出现。
KMP算法在字符串很长的时候性能比较突出，但是字符串长度一般时性能没有普通的遍历性能好，因此java8使用的方式仍然是普通解法

代码编写

java语言版本

方案一：

    public static boolean isContain(MyTreeNode r1, MyTreeNode r2){
        if (r1 == null && r2 == null){
            return true;
        }else if (r2 == null || r1 == null){
            return false;
        }
        return isContain2(r1, r2)
                || isContain(r1.getLeft(), r2)
                || isContain(r1.getRight(), r2);

    }

    private static boolean isContain2(MyTreeNode r1, MyTreeNode r2) {
        if (r1 == null && r2 == null){
            return true;
        }else if (r2 == null || r1 == null){
            return false;
        }
        return r1.getData().equals(r2.getData())
                && isContain2(r1.getLeft(), r2.getLeft())
                && isContain2(r1.getRight(), r2.getRight());
    }

方案二：

    /**
     * **进阶解法：
     * 1、将t1和t2进行序列化后，判断t1是否存在t2的子串即可
     * 2、难点，不可使用String.contains,需要使用线性复杂度的KMP算法
     * @return
     */
    public static boolean contains3(MyTreeNode t1, MyTreeNode t2){
        String serial1 = SerialTree.serial1(t1);
        String serial2 = SerialTree.serial1(t2);
        if(serial1.contains(serial2)){
            return true;
        }else {
            return false;
        }
        //  考虑到str很长时，contains算法的场景性能没有KMP好，所以使用KMP算法判断
    }

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题其实只要掌握递归我认为在算法面试的时候解答起来非常的快，如果非要使用kmp算法的话，那么撕起来一定挺麻烦的，价值不高，主要提供两种思路来解决树之间判断包含关系类型的问题：
1、递归判断每一个子树是否包含
2、序列化成字符串直接判断序列化结果是否包含

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！