题解 | #判断t1树是否包含t2树全部的拓扑结构#

通过CD170 判断t1树是否包含t2树全部的拓扑结构 改写即可，时间复杂度 O(n * m)
代码如下：

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Stack;
class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;

 public TreeNode(int val) {
     this.val = val;
 }
}
class ScannerInfo {
 int rootNum;
 int[][] info;
 public ScannerInfo(int rootNum, int[][] info) {
     this.rootNum = rootNum;
     this.info = info;
 }
}
public class Main {
 static Map<Integer,TreeNode> cache = new HashMap<>(16);

 public static void main(String[] args) {
     Scanner scanner = new Scanner(System.in);
     while(scanner.hasNext()) {
         ScannerInfo bigTreeScannerInfo = scannerInfo(scanner);
         TreeNode bigTree = constructTree(bigTreeScannerInfo.rootNum, bigTreeScannerInfo.info);
         ScannerInfo smallTreeScannerInfo = scannerInfo(scanner);
         TreeNode smallTree = constructTree(smallTreeScannerInfo.rootNum, smallTreeScannerInfo.info);
         System.out.printf("%s\n", String.valueOf(isSubTree(bigTree, smallTree)));
     }
 }

 private static boolean isSubTree(TreeNode big, TreeNode small) {
     boolean result1 = check(big, small);
     boolean result2 = check(big.left, small);
     boolean result3 = check(big.right,small);
     return result1 || result2 || result3;
 }

 private static boolean check(TreeNode big, TreeNode small) {
     if (big == null && small == null) {
         return true;
     }
     if (big == null || small == null) {
         return false;
     }
     if (big.val != small.val) {
         return check(big.left, small) || check(big.right,small);
     }
     return check(big.left, small.left) && check(big.right, small.right);
 }

 private static ScannerInfo scannerInfo(Scanner scanner) {
     int treeNum = scanner.nextInt();
     int treeRootNum = scanner.nextInt();
     int temp = treeNum;
     int i = 0;
     int[][] info = new int[treeNum][3];
     while(temp > 0) {
         info[i][0] = scanner.nextInt();
         info[i][1] = scanner.nextInt();
         info[i][2] = scanner.nextInt();
         i++;
         temp--;
     }
     ScannerInfo scannerInfo = new ScannerInfo(treeRootNum, info);
     return scannerInfo;
 }

 private static TreeNode constructTree(int rootNum, int[][] info) {
     cache = new HashMap<>();
     if (info == null || info.length == 0 || rootNum == 0) {
         return null;
     }
     for(int i = 0;i < info.length;i++) {
         TreeNode cur = getOrPutFromCache(info[i][0]);
         TreeNode left = getOrPutFromCache(info[i][1]);
         TreeNode right = getOrPutFromCache(info[i][2]);
         cur.left = left;
         cur.right = right;
     }
     return cache.get(rootNum);

 }

 private static TreeNode getOrPutFromCache(int num) {
     if (num == 0) {
         return null;
     }
     TreeNode result = cache.get(num);
     if (result == null) {
         result = new TreeNode(num);
         cache.put(num, result);
     }

     return result;
 }
}

先序遍历序列化树，借助String的contains方法判断是否是子串，时间复杂度O(n+m)

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Stack;
class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;

 public TreeNode(int val) {
     this.val = val;
 }
}
class ScannerInfo {
 int rootNum;
 int[][] info;
 public ScannerInfo(int rootNum, int[][] info) {
     this.rootNum = rootNum;
     this.info = info;
 }
}
public class Main {
 static Map<Integer,TreeNode> cache = new HashMap<>(16);

 public static void main(String[] args) {
     Scanner scanner = new Scanner(System.in);
     while(scanner.hasNext()) {
         ScannerInfo bigTreeScannerInfo = scannerInfo(scanner);
         TreeNode bigTree = constructTree(bigTreeScannerInfo.rootNum, bigTreeScannerInfo.info);
         ScannerInfo smallTreeScannerInfo = scannerInfo(scanner);
         TreeNode smallTree = constructTree(smallTreeScannerInfo.rootNum, smallTreeScannerInfo.info);
         String bigStr = preSerialize(bigTree);
         String smallStr = preSerialize(smallTree);
         boolean result = bigStr.contains(smallStr);
         System.out.printf("%s\n", String.valueOf(result));
     }
 }

 private static String preSerialize(TreeNode root) {
     if (root == null) {
         return "#!";
     }
     String res = root.val + "!";
     res += preSerialize(root.left);
     res += preSerialize(root.right);
     return res;
 }
 private static ScannerInfo scannerInfo(Scanner scanner) {
     int treeNum = scanner.nextInt();
     int treeRootNum = scanner.nextInt();
     int temp = treeNum;
     int i = 0;
     int[][] info = new int[treeNum][3];
     while(temp > 0) {
         info[i][0] = scanner.nextInt();
         info[i][1] = scanner.nextInt();
         info[i][2] = scanner.nextInt();
         i++;
         temp--;
     }
     ScannerInfo scannerInfo = new ScannerInfo(treeRootNum, info);
     return scannerInfo;
 }

 private static TreeNode constructTree(int rootNum, int[][] info) {
     cache = new HashMap<>();
     if (info == null || info.length == 0 || rootNum == 0) {
         return null;
     }
     for(int i = 0;i < info.length;i++) {
         TreeNode cur = getOrPutFromCache(info[i][0]);
         TreeNode left = getOrPutFromCache(info[i][1]);
         TreeNode right = getOrPutFromCache(info[i][2]);
         cur.left = left;
         cur.right = right;
     }
     return cache.get(rootNum);

 }

 private static TreeNode getOrPutFromCache(int num) {
     if (num == 0) {
         return null;
     }
     TreeNode result = cache.get(num);
     if (result == null) {
         result = new TreeNode(num);
         cache.put(num, result);
     }

     return result;
 }
}

把String的contains替换成自己实现KMP算法

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Stack;
class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;

 public TreeNode(int val) {
     this.val = val;
 }
}
class ScannerInfo {
 int rootNum;
 int[][] info;
 public ScannerInfo(int rootNum, int[][] info) {
     this.rootNum = rootNum;
     this.info = info;
 }
}
public class Main {
 static Map<Integer,TreeNode> cache = new HashMap<>(16);

 public static void main(String[] args) {
     Scanner scanner = new Scanner(System.in);
     while(scanner.hasNext()) {
         ScannerInfo bigTreeScannerInfo = scannerInfo(scanner);
         TreeNode bigTree = constructTree(bigTreeScannerInfo.rootNum, bigTreeScannerInfo.info);
         ScannerInfo smallTreeScannerInfo = scannerInfo(scanner);
         TreeNode smallTree = constructTree(smallTreeScannerInfo.rootNum, smallTreeScannerInfo.info);
         String bigStr = preSerialize(bigTree);
         String smallStr = preSerialize(smallTree);
         boolean result = getIndexOf(bigStr, smallStr) != -1;
         System.out.printf("%s\n", String.valueOf(result));
     }
 }

 private static int getIndexOf(String s, String m) {
     if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
         return -1;
     }
     char[] ss = s.toCharArray();
     char[] ms = m.toCharArray();
     int si = 0;
     int mi = 0;
     int[] next = getNextArray(ms);
     while(si < ss.length && mi < ms.length) {
         if (ss[si] == ms[mi]) {
             si++;
             mi++;
         } else if (next[mi] ==  -1) {
             si++;
         } else {
             mi = next[mi];
         }
     }
     return mi == ms.length ? si - mi : -1;
 }

 private static int[] getNextArray(char[] ms) {
     if (ms.length == 1) {
         return new int[]{-1};
     }
     int[] next = new int[ms.length];
     next[0] = -1;
     next[1] = 0;
     int cn = 0;
     int pos = 2;
     while(pos < next.length) {
         if (ms[pos - 1] == ms[cn]) {
             next[pos++] = ++cn;
         } else if (cn > 0) {
             cn = next[cn];
         } else {
             next[pos++] = 0;
         }
     }
     return next;
 }

 private static String preSerialize(TreeNode root) {
     if (root == null) {
         return "#!";
     }
     String res = root.val + "!";
     res += preSerialize(root.left);
     res += preSerialize(root.right);
     return res;
 }

 private static ScannerInfo scannerInfo(Scanner scanner) {
     int treeNum = scanner.nextInt();
     int treeRootNum = scanner.nextInt();
     int temp = treeNum;
     int i = 0;
     int[][] info = new int[treeNum][3];
     while(temp > 0) {
         info[i][0] = scanner.nextInt();
         info[i][1] = scanner.nextInt();
         info[i][2] = scanner.nextInt();
         i++;
         temp--;
     }
     ScannerInfo scannerInfo = new ScannerInfo(treeRootNum, info);
     return scannerInfo;
 }

 private static TreeNode constructTree(int rootNum, int[][] info) {
     cache = new HashMap<>();
     if (info == null || info.length == 0 || rootNum == 0) {
         return null;
     }
     for(int i = 0;i < info.length;i++) {
         TreeNode cur = getOrPutFromCache(info[i][0]);
         TreeNode left = getOrPutFromCache(info[i][1]);
         TreeNode right = getOrPutFromCache(info[i][2]);
         cur.left = left;
         cur.right = right;
     }
     return cache.get(rootNum);

 }

 private static TreeNode getOrPutFromCache(int num) {
     if (num == 0) {
         return null;
     }
     TreeNode result = cache.get(num);
     if (result == null) {
         result = new TreeNode(num);
         cache.put(num, result);
     }

     return result;
 }
}