python递归解法

# -*- 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
        def cmp(p1,p2):#递归比对函数
            if not p2:#  p2都没有了 说明比较完成 各个结点相等
                return True
            if not p1:#  p1有一个没有了说明p2不是子树 
                return False
            if p1.val!=p2.val:
                return False
            return cmp(p1.left,p2.left) and cmp(p1.right,p2.right)#分别递归比对各自的左右子树

        #开始比较
        if not pRoot2 or not pRoot1:
            return False

        f=False
        if  pRoot1 and pRoot2:
            if pRoot1.val==pRoot2.val:  #找到第一个相等的结点开始递归比对
                if cmp(pRoot1,pRoot2):
                    f=True 
            if not f and pRoot1.left:   #如果不是子树且pRoot1.left存在 
                if  self.HasSubtree( pRoot1.left, pRoot2):
                    f=True
            if not f and pRoot1.right:  #如果不是子树且pRoot1.right存在  
                if self.HasSubtree( pRoot1.right, pRoot2):
                    f=True
            return f