572. Subtree of Another Tree

Loading...LeetCode

BFS遍历 s tree, 逐个node去判断是否等于t tree.

主要是判断过程也需要 recursive 写，感觉这题难度不该标easy啊...

BFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        
        # 相等判断函数
        def equal(i, j):
            if not i and not j: return True
            elif not i or not j: return False
            else:
                return i.val == j.val and equal(i.left, j.left) and equal(i.right, j.right)
        
        # BFS
        if not s: return False
        q = collections.deque([s])
        while q:
            node = q.pop()
            if equal(node, t): return True
            else:
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
        return False

DFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s: return False
        if self.sameTree(s, t):
            return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
    
    def sameTree(self, s, t):
        if not s and not t: return True
        elif not s or not t: return False
        return False if s.val != t.val else (self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right))