t1是一棵含有幾百萬個節點的樹，t2含有幾百個節點。判斷t2是否是t1 的子樹。
首先考慮小資料量的情況，可以根據樹的前序和中序周遊所得的字元串，來通過判斷t2生成的字元串是否是t1字元串的子串，來判斷t2是否是t1的子樹。假設t1的節點數為n，t2的節點數為m。周遊兩棵樹算法時間複雜性是o(n + m)， 判斷字元串是否為另一個字元串的子串的複雜性也是o( n + m)（比如使用kmp算法）。所需要的空間也是o(n + m)。
這裡有一個問題需要注意：對于左節點或者右節點為null的情況，需要在字元串中插入特殊字元表示。否則對于下面這種情形将會判斷錯誤：
是以如果插入特殊字元，上述兩棵樹的中序和前序周遊的結果是相同的。
由于本例有幾百萬的節點，需要占用o(n + m)的記憶體。
如果換一種思路，就是周遊t1，每當t1的某個節點與t2的根節點值相同時，就判斷兩棵子樹是否相同。這個算法的複雜度是o(n*m)。我們再仔細思考一下。因為隻有在節點值與t2的根節點值相同才會調用o(m)。假設有k次這種情況，那麼算法的複雜度就是o(n + k*m)。下面是代碼實作：
對于上面讨論的2種解法，哪種解法比較好呢？其實有必要好好讨論一番：
1）方法一會占用o(n + m)的記憶體，而另外一種解法隻會占用o(logn + logm)的記憶體（遞歸的棧記憶體）。當考慮scalability擴充性時，記憶體使用的多寡是個很重要的因素。
2）方法一的時間複雜度為o(n + m)，方法二最差的時間複雜度是o(n*m)。是以要通過工程實踐或者是曆史資料看一下哪種方法更優。當然了，方法二也可能會很早發現兩棵樹的不同，早早的退出了checksubtree。
總的來說，在空間使用上，方法二更好。在時間上，需要通過實際資料來驗證。