首页 > 代码库 > 【剑指offer】Q18:树的子结构

【剑指offer】Q18:树的子结构

类似于字符串的匹配,我们总是找到第一个匹配的字符,在继续比較以后的字符是否所有同样,假设匹配串的第一个字符与模式串的第一个不同样,我们就去查看匹配串的下一个字符是否与模式串的第一个同样,相应到这里,就是我们要遍历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)


【剑指offer】Q18:树的子结构