首页 > 其他 > 详细

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

时间:2014-07-08 20:43:05      阅读:287      评论:0      收藏:0      [点我收藏+]

类似于字符串的匹配,我们总是找到第一个匹配的字符,在继续比较以后的字符是否全部相同,如果匹配串的第一个字符与模式串的第一个不相同,我们就去查看匹配串的下一个字符是否与模式串的第一个相同,对应到这里,就是我们要遍历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:树的子结构,布布扣,bubuko.com

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

原文:http://blog.csdn.net/shiquxinkong/article/details/37353429

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!