题解 | #树的子结构#

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

• 根据题意可知，需要一个函数判断树A和树B是否有相同的结构。显然是个递归程序。
• 递归函数的功能：判断2个数是否有相同的结构，如果相同，返回true，否则返回false
• 递归终止条件：如果树B为空，返回true，此时，不管树A是否为空，都为true。否则，如果树B不为空，但是树A为空，返回false，此时B还没空但A空了，显然false
• 下一步递归参数： 如果A的根节点和B的根节点不相等，直接返回false。 否则，相等，就继续判断A的左子树和B的左子树，A的右子树和B的右子树

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        re = False
        if pRoot1 and pRoot2:
            if pRoot1.val == pRoot2.val:
                re = self.Same(pRoot1, pRoot2)
            if not re:
                re = self.HasSubtree(pRoot1.left, pRoot2)
            if not re:
                re = self.HasSubtree(pRoot1.right, pRoot2)
        return re

    def Same(self, p1, p2):
        if not p2:
            return True
        if not p1:
            return False
        return p1.val == p2.val and self.Same(p1.left, p2.left) and self.Same(p1.right, p2.right)