题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
题目地址
思路
如果树1或树2为空时，返回False
在树1中找到和树2一样的根结点R，然后在判断树1中以R为根结点的子树是否与树2有一样的结构。
先以树1 的根结点为起点寻找是否包含树B，如果找不到就以树A的左结点为起点寻找，若还找不到，以树A的右结点为起点寻找，递归进行
Python
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self,x):
self.val = x
self.left = None
self.right = None node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node1.left = node2
node2.right = node3
node3.left = node4
node3.right = node5 class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if not pRoot1 or not pRoot2:
return False
result = False
if pRoot1.val == pRoot2.val:
# 找到根结点相同的结点
result = self.isSubTree(pRoot1, pRoot2)
if not result:
# 没找到，在左子树寻找
result = self.HasSubtree(pRoot1.left, pRoot2)
if not result:
# 还没找到，在右子树寻找
result = self.HasSubtree(pRoot1.right, pRoot2)
return result def isSubTree(self,tree1, tree2):
if not tree2:
return True
if not tree1:
return False
if tree1.val != tree2.val:
return False
return self.isSubTree(tree1.left,tree2.left) and self.isSubTree(tree1.right,tree2.right) if __name__ == '__main__':
result = Solution().HasSubtree(node1, node3)
print(result)