572. 另一個(gè)樹(shù)的子樹(shù)

來(lái)源: 572. 另一個(gè)樹(shù)的子樹(shù)

1. 題目描述

給定兩個(gè)非空二叉樹(shù) s 和 t，檢驗(yàn) s 中是否包含和 t 具有相同結(jié)構(gòu)和節(jié)點(diǎn)值的子樹(shù)。s 的一個(gè)子樹(shù)包括 s 的一個(gè)節(jié)點(diǎn)和這個(gè)節(jié)點(diǎn)的所有子孫。s 也可以看做它自身的一棵子樹(shù)

2. 解題思路

遞歸，isSameTree檢測(cè)樹(shù)是否相同

3. 代碼

class Solution:
    def isSameTree(self, s, t):
        if s is not None and t is not None and s.val == t.val:
            return self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)
        if s is None and t is None:
            return True
        return False


    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if t is None:
            return True
        if s is None:
            return False
        if s is not None and t is not None:
            if self.isSameTree(s, t) == True:
                return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)