# 572. Subtree of Another Tree

# Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

# Example 1:
# Given tree s:

#      3
#     / \
#    4   5
#   / \
#  1   2
# Given tree t:
#    4
#   / \
#  1   2
# Return true, because t has the same structure and node values with a subtree of s.


# Example 2:
# Given tree s:

#      3
#     / \
#    4   5
#   / \
#  1   2
#     /
#    0
# Given tree t:
#    4
#   / \
#  1   2
# Return false.

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def isMatch(self, s, t):
        if not(s and t):
            return s is t
        return (s.val == t.val and self.isMatch(s.left, t.left) and self.isMatch(s.right, t.right))

    def isSubtree(self, s, t):
        if self.isMatch(s, t):
            return True
        if not s:
            return False
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

1a92a2d9577473b30ff17e9a5d9efee42ee4d9f1
<mask token>


class Solution(object):

    def isMatch(self, s, t):
        if not (s and t):
            return s is t
        return s.val == t.val and self.isMatch(s.left, t.left
            ) and self.isMatch(s.right, t.right)
    <mask token>

<mask token>


class Solution(object):

    def isMatch(self, s, t):
        if not (s and t):
            return s is t
        return s.val == t.val and self.isMatch(s.left, t.left
            ) and self.isMatch(s.right, t.right)

    def isSubtree(self, s, t):
        if self.isMatch(s, t):
            return True
        if not s:
            return False
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

class TreeNode(object):
    <mask token>


class Solution(object):

    def isMatch(self, s, t):
        if not (s and t):
            return s is t
        return s.val == t.val and self.isMatch(s.left, t.left
            ) and self.isMatch(s.right, t.right)

    def isSubtree(self, s, t):
        if self.isMatch(s, t):
            return True
        if not s:
            return False
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

class TreeNode(object):

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):

    def isMatch(self, s, t):
        if not (s and t):
            return s is t
        return s.val == t.val and self.isMatch(s.left, t.left
            ) and self.isMatch(s.right, t.right)

    def isSubtree(self, s, t):
        if self.isMatch(s, t):
            return True
        if not s:
            return False
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

# 572. Subtree of Another Tree

# Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

# Example 1:
# Given tree s:

#      3
#     / \
#    4   5
#   / \
#  1   2
# Given tree t:
#    4
#   / \
#  1   2
# Return true, because t has the same structure and node values with a subtree of s.


# Example 2:
# Given tree s:

#      3
#     / \
#    4   5
#   / \
#  1   2
#     /
#    0
# Given tree t:
#    4
#   / \
#  1   2
# Return false.

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def isMatch(self, s, t):
        if not(s and t):
            return s is t
        return (s.val == t.val and self.isMatch(s.left, t.left) and self.isMatch(s.right, t.right))

    def isSubtree(self, s, t):
        if self.isMatch(s, t):
            return True
        if not s:
            return False
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
