类似于字符串的匹配，我们总是找到第一个匹配的字符，在继续比較以后的字符是否所有同样，假设匹配串的第一个字符与模式串的第一个不同样，我们就去查看匹配串的下一个字符是否与模式串的第一个同样，相应到这里，就是我们要遍历root1，找到与root2同样的第一个结点，若root1的根不同样，那么我们查找其左子树是否有第一个同样的，同样的操作再去看右子树是否有同样的第一个，若找到了第一个同样的，与字符串匹配思想一样，字符串匹配中，是比較以后的字符是否所有同样，这里我们比較其左右子树是否 也相应同样，若找到了一个，则结束。

# Q18: subtree

def HasSubTree(root1, root2):

	re = False

	# None is subTree of anyone

	if root2 == None:

		return True

	# root1 is None, but root2 is not None

	if root1 == None:

		return False

	# subtree can start from this node

	if root1.val == root2.val:

		re = DoesTree1HasTree2(root1, root2)

	# subtree may be in root1's left branch

	if re == False and root1.left:

		re = DoesTree1HasTree2(root1.left, root2)

	# subtree may be in root1's right branch

	if re == False and root1.right:

		re = DoesTree1HasTree2(root1.right, root2)

	return re

def DoesTree1HasTree2(root1, root2):

	if root2 == None:

		return True

	if root1 == None:

		return False

	if root1.val != root2.val:

		return False

	return DoesTree1HasTree2(root1.left, root2.left) and \

			DoesTree1HasTree2(root1.right, root2.right)