树的子结构

题目描述

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

思路

把B树从A的根开始比较，如果相等就比较两棵树是否相同，如果不相同，再从A树的左、右子树开始与B比。 整体思路就是遍历A的全部节点，一旦发现这个节点与B的根相等，那么比较A当前节点的子树是否与B相等。 这个比较的过程使用递归的方法。
当B已经是空结点时，说明B已经被比完了，返回正确。
若A已经是空，而B不是空，说明A此刻的子树比B小，返回错误。
剩下的情况就是递归的比较当前二者的根节点是否相同，然后递归到左右子树。

代码

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        if pRoot1 == None or pRoot2 == None:
            return False
        result = False
        if pRoot1.val == pRoot2.val:
            result = self.sameTree(pRoot1,pRoot2)
        if result is False:
            result = self.HasSubtree(pRoot1.left, pRoot2)
        if result is False:
            result = self.HasSubtree(pRoot1.right, pRoot2)
        return result
    def sameTree(self,p1,p2):
        if p2 is None:
            return True #证明B树的全部节点被比完了
        if p1 is None:
            return False #B树的节点还没比完 A就空了
        #接下来比较当前节点，相等->递归比较后续节点，不相等->直接返回错误
        if p1.val != p2.val:
            return False
        if p1.val == p2.val: #当前节点相等了
            flag_left = self.sameTree(p1.left,p2.left) #比较左子树
            flag_right = self.sameTree(p1.right,p2.right)#比较右子树
            return flag_left and flag_right