原文：
You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1
译文：
有两棵很大的二叉树：T1有上百万个结点，T2有上百个结点。写程序判断T2是否为T1的子树。
思路：
1） 因为中序前序遍历就可以决定一棵树，把两棵树的中序前序都写出来，如果两个遍历中T2都是T1的子串，可以确定T2是T1的子树。
当然这会遇到无法区分
的情况。因为
T1, in order: 3,3 T1, pre order 3,3< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+ClQyLCBpbiBvcmRlcjogMywzICAgIFQyLCBwcmUgb3JkZXIgMywzPGJyPgo8L3A+CjxwPgrL+dLUsdjQ69Kyy+PI6251bGy92rXjo6zL+dLUPC9wPgo8cD4KPC9wPgo8cD4KVDEsIGluIG9yZGVyOiAwLCAzLCAwLCAzLCAwICAgIFQxLCBwcmUgb3JkZXIgMywgMywgMCwgMCwgMDwvcD4KPHA+ClQyLCBpbiBvcmRlcjogMCwgMywgMCwgMywgMCAgICBUMiwgcHJlIG9yZGVyIDMsIDAsIDMsIDAsIDA8YnI+CjwvcD4K1eLW1re9t6jKsbzkuLTU07bIo7pPKG4mIzQzO20pLCC/1bzkuLTU07bIo7pPKG4mIzQzO20pICwgbixtt9ax8M6qwb249sr3tcS92rXjyv2ho7WxuqPBv8r9vt3KsbK7ysrTw6OhCjxicj4KCjKjqbXduemjobTTuPm92rXjzfnPwrXduemjrMXQts/X08r3yse38bTm1NrG5LXE1/PX08r3u/LT0tfTyvfE2qGjCsqxvOS4tNTTtsijuk8obm0pLCC/1bzkuLTU07bIo7pPKGxvZyhuKQogJiM0MzsgbG9nKG0pKQq1q8q1vMrJz6Os1NrV5sq1tcTUy9DQyrGjrLXduem82cjnt6LP1sL61+PX08r3tcTM9bz+vs3Wsb3Tt7W72KOstviyu7vhvMzQ+LLp1dKho9LytMu13bnpt6jU2sq1vMrW0M7ewtvKsbzkv9W85Lj808WjoQo8YnI+Cgo8cHJlIGNsYXNzPQ=="brush:java;">package Tree_Graph; import CtCILibrary.AssortedMethods; import CtCILibrary.TreeNode; public class S4_8 { // 判断t2是否是t1的子树 public static boolean isSubTree(TreeNode t1, TreeNode t2) { if(t2 == null) { // 空树始终是另一个树的子树 return true; } if(t1 == null) { // 此时r2非空，非空树不可能是一个空树的子树 return false; } if(t1.data == t2.data) { // 找到两树匹配 if(isSameTree(t1, t2)){ return true; } } // 继续在r1的左子树和右子树里找匹配 return isSubTree(t1.left, t2) || isSubTree(t1.right, t2); } // 判断两棵树是否相同 public static boolean isSameTree(TreeNode t1, TreeNode t2) { if(t1==null && t2==null) { return true; } if(t1==null || t2==null) { return false; } if(t1.data != t2.data) { return false; } return isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right); } public static void main(String[] args) { // t2 is a subtree of t1 int[] array1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}; int[] array2 = {2, 4, 5, 8, 9, 10, 11}; TreeNode t1 = AssortedMethods.createTreeFromArray(array1); TreeNode t2 = AssortedMethods.createTreeFromArray(array2); if (isSubTree(t1, t2)) System.out.println("t2 is a subtree of t1"); else System.out.println("t2 is not a subtree of t1"); // t4 is not a subtree of t3 int[] array3 = {1, 2, 3}; TreeNode t3 = AssortedMethods.createTreeFromArray(array1); TreeNode t4 = AssortedMethods.createTreeFromArray(array3); if (isSubTree(t3, t4)) System.out.println("t4 is a subtree of t3"); else System.out.println("t4 is not a subtree of t3"); } }