java數據結構與算法刷題目錄（劍指Offer、LeetCode、ACM）-----主目錄-----持續更新(進不去說明我沒寫完)：https://blog.csdn.net/grd_java/article/details/123063846

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表示右子樹為空情況

5. 生成兩顆樹的匹配串后，讓大樹作為主字符串，要匹配的子樹作為要匹配的子串，改編KMP算法，如果匹配成功，說明樹中可以匹配到子樹

代碼:leetcode的特色之一就是，更優的算法，有時因為使用程序自帶的特殊容器（比如Java中的List），因為這些容器初始化比較耗時間，反而耗時更高。但是實際工作場景，一旦數據量起來，肯定是這個算法優于上面的暴力解法的。

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繼續遍歷右子樹，否則填充rNullif (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;}
}