方法：利用KMP算法，將兩個樹進行序列化，分別遍歷一遍樹，得到兩個字符串，時間復(fù)雜度是O(n)

KMP問題：
String1，String2，如果String2為String1的子串，則返回String2在String1中的開始位置

public 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; } public 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 pos = 2;int cn = 0;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; }

總結(jié)

以上是生活随笔為你收集整理的利用KMP算法判断一个树是否是另一个树的子树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。