剑指 匹配树的子结构

第一步 找到 子树A中与子树B中根节点一样的位置
第二步 判断完根节点判断以此为根节点的左子树与右子树是否相等
其中需要注意 A 或者 A 的左子树 或是 A的右子树有一个包含B子树就可以了。
同时需要注意or and 逻辑运算符判断前后问题。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def issub(self,a,b):
        if b==None:
            return True

        if  a==None or a.val!=b.val :
            return False

        return self.issub(a.left,b.left) and self.issub(a.right,b.right)
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if pRoot1 ==None or pRoot2==None:
            return False

        return self.issub(pRoot1,pRoot2) or self.HasSubtree(pRoot1.left,pRoot2) or self.HasSubtree(pRoot1.right,pRoot2)