【剑指offer】数的子结构（python）

题目描述：

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解题思路：
判断二叉树B是否为二叉树A的子结构，需要分为两步进行实现：
1、递归遍历二叉树A，若A当前节点的值与二叉树B父节点相等，则判断A当前节点所在的子树是否存在与二叉树B相同的子树。
2、判断当前节点下是否存在与二叉树B相同的子树。
代码及解析：（以注释的方式添加解析）

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot1 or not pRoot2:  # 若两棵树其中一棵为空，返回False
            return False
        result = False   # 初始化结果值
        if (pRoot1.val == pRoot2.val):       # 若当前节点的值与pRoot2的节点值相等，则判断当前节点是否存在与pRoot2相等的子树
            result = self.is_equal(pRoot1, pRoot2)
         # 若当前节点下不存在与pRoot2相等的子树，则递归判断当前节点的左子树和右子树是否存在与pRoot2相等的子树
        if not result:  
            result = self.HasSubtree(pRoot1.left, pRoot2)
        if not result:
            result = self.HasSubtree(pRoot1.right, pRoot2)
        return result
        
    def is_equal(self, pRoot1, pRoot2):
        if not pRoot2:   # 若pRoot2为空，证明递归过程中一直没有触发返回False的条件，直接返回True
            return True
        if not pRoot1:
            return False
        result = True
        # 判断pRoot1当前节点的值是否等于pRoot2当前节点的值
        if pRoot1.val != pRoot2.val:
            result = False
         # 若pRoot1当前节点的值等于pRoot2当前节点的值，则递归判断左子树和右子树是否相等
        if result:
            result = self.is_equal(pRoot1.left, pRoot2.left)
        if result:
            result = self.is_equal(pRoot1.right, pRoot2.right)
        return result