[NC]98 另一棵树的子树（完全相同）

🚩传送门：牛客题目
力扣题目

题目

给你两棵二叉树 root 和 subRoot。检验 root中是否包含和 subRoot具有相同结构和节点值的子树。如果存在，返回 true；否则，返回 false。

二叉树的一棵子树包括某个节点和这个节点的所有后代节点。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2] 输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] 输出：false

解题思路：深度优先搜索暴力匹配

这是一种最朴素的方法——深度优先搜索枚举 s中的每一个节点作为根节点与子树进行匹配，判断这个点作为根节点其子树是否和t相等。如何判断一个节点的子树是否和t相等呢，我们又需要做一次深度优先搜索来检查，即让两个指针一开始先指向该节点和 t 的根，然后「同步移动」两根指针来「同步遍历」这两棵树，判断对应位置是否相等。

复杂度分析

时间复杂度：，对于每一个 上的点，都需要做一次深度优先搜索来和 匹配，匹配一次
的时间代价是 ，那么总的时间代价就是。故渐进时间复杂度为。

空间复杂度：，假设 深度为 ，假设 深度为 ，任意时刻栈空间的最大使用
代价是，故渐进空间复杂度为。

我的代码

class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        return dfs(s, t);
    }
    public boolean dfs(TreeNode s, TreeNode t) {
        if (s == null) return false;
        if (check(s, t)) return true;                // 1. 检查当前结点为根是否可行
        return dfs(s.left, t) || dfs(s.right, t);    // 2. 递归左右子树
    }
    public boolean check(TreeNode s, TreeNode t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null || s.val != t.val) {
            return false;
        }
        return check(s.left, t.left) && check(s.right, t.right);
    }
}

解题思路：深度优先搜索序列上做串匹配

这个方法需要我们先了解一个「常识」：一棵子树上的点在先序遍历中是连续的。我们可以确定解决这个问题的方向就是：把s和t先转换成深度优先搜索序列（先序遍历序列），然后看t的深度优先搜索序列是否是s的深度优先搜索序列的「子串」。

这样做正确吗？如下图可示

由此可见「s 的深度优先搜索序列包含t的深度优先搜索序列」是「t是 s子树」的必要不充分条件，所以单纯这样做是不正确的。

34125 包含了字串的 41 ，但显然不是其子串

🚩为了解决这个问题，我们可以引入两个空值 lNull 和 rNull，当一个节点的左孩子或者右孩子为空的时候，就插入这两个空值，这样深度优先搜索序列就唯一对应一棵树。处理完之后，就可以通过判断「s 的深度优先搜索序列包含 t 的深度优先搜索序列」来判断答案。

在判断「s 的深度优先搜索序列包含 t 的深度优先搜索序列」的时候，可以暴力匹配，也可以使用 KMP 或者 Rabin-Karp 算法，在使用 Rabin-Karp 算法的时候，要注意串中可能有负值。这里给出用 KMP 判断的代码实现。

复杂度分析

时间复杂度：，遍历两棵树得到深度优先搜索序列的时间代价是，在匹配的时
候，如果使用暴力匹配，时间代价为，使用 或 进行串匹配的时间代
价都是 ，由于这里的代码使用 实现的，所以渐进时间复杂度为。

空间复杂度：，这里保存了两个深度优先搜索序列，还计算了长度的 数组，
辅助空间的总代价为 ，任意时刻栈空间的最大使用代价是，然而由于这
，故渐进空间复杂度为 。

🚩我的代码

public class Solution {
public boolean isContains (TreeNode root1, TreeNode root2) {
        // write code here
        StringBuffer res1=new StringBuffer();
        StringBuffer res2=new StringBuffer();
        preOrder(root1,res1);
        preOrder(root2,res2);
        if(res1.toString().contains(res2.toString()))return true;    // 重点调用 contains
        return false;
    }
    public void preOrder(TreeNode root,StringBuffer res){
        if(root==null)return;
        res.append(root.val);
        if(root.left==null) res.append("#1");
        else preOrder(root.left,res);
        if(root.right==null) res.append("#2");
        else preOrder(root.right,res);
    }
}

😱原封代码

需要自己手撸KMP的原装代码，人嘛了。

class Solution {
    int lNull, rNull;
    public boolean isSubtree(TreeNode s, TreeNode t) {
        List<Integer> sOrder = new ArrayList<Integer>();    // 存储s先序遍历结果
        List<Integer> tOrder = new ArrayList<Integer>();    // 存储t先序遍历结果
        lNull = Integer.MAX_VALUE - 1;                        // 左子树为空标记符
        rNull = Integer.MAX_VALUE;                            // 右子树为空标记符
        getDfsOrder(s, sOrder);                                // 获取 s 的先序遍历序列
        getDfsOrder(t, tOrder);                                // 获取 t 的先序遍历序列
        return kmp();                                        // 返回二者 Kmp 的比较结果
    }
    public void getDfsOrder(TreeNode t, List<Integer> preOrder) {
        if (t == null) return;
        preOrder.add(t.val);                                // 1. 添加当前结点
        if (t.left != null) getDfsOrder(t.left, preOrder);    // 2. 左子树不空递归左子树
        else preOrder.add(lNull);                            // 2. 添加 lNull 标识符
        if (t.right != null) getDfsOrder(t.right, preOrder);// 3. 右子树不空递归右子树
        else preOrder.add(rNull);                            // 3. 添加 rNull 标识符
    }
    public boolean kmp(List<Integer> sOrder,List<Integer> tOrder) {
        int sLen = sOrder.size(), tLen = tOrder.size();
        int[] fail = new int[tOrder.size()];
        Arrays.fill(fail, -1);
        for (int i = 1, j = -1; i < tLen; ++i) {
            while (j != -1 && !(tOrder.get(i).equals(tOrder.get(j + 1)))) {
                j = fail[j];
            }
            if (tOrder.get(i).equals(tOrder.get(j + 1))) {
                ++j;
            }
            fail[i] = j;
        }
        for (int i = 0, j = -1; i < sLen; ++i) {
            while (j != -1 && !(sOrder.get(i).equals(tOrder.get(j + 1)))) {
                j = fail[j];
            }
            if (sOrder.get(i).equals(tOrder.get(j + 1))) {
                ++j;
            }
            if (j == tLen - 1) {
                return true;
            }
        }
        return false;
    }
}