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

1. 暴力求解，深度优先

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2. KMP算法进行串匹配

1. 生成两颗树的遍历序列，以类似如下的形式：（下面形式是广度（层序）遍历序列，需要额外空间辅助，所以我们放弃）
   
2. 为了效率和更少的空间，我们使用广度优先遍历。那么就需要两个不同的值，来表示某结点左子树为空，和右子树为空的情况。
3. 同样为了效率，我们不使用字符串比较，选用int型容器，比如int型的链表来生成匹配串
4. 那么null如何来表示呢？

1. 我们可以规定两个值，来分别表示左子树为null和右子树为null的情况
2. 这里我选择先找到树中最大值max，然后令max+1表示左子树为空情况，max+2表示右子树为空情况

5. 生成两颗树的匹配串后，让大树作为主字符串，要匹配的子树作为要匹配的子串，改编KMP算法，如果匹配成功，说明树中可以匹配到子树

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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59