LC-0572 Easy LeetCode

572. Subtree of Another Tree

Tree Depth-First Search String Matching Binary Tree Hash Function

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 50% Topics: Tree, Depth-First Search, String Matching, Binary Tree, Hash Function

Reading material

Trees & Traversals 18 min String Matching & Hashing 13 min Arrays & Hashing 12 min

Reference solution (spoiler · python)

# Time:  O(m * n), m is the number of nodes of s, n is the number of nodes of t
# Space: O(h), h is the height of s

class Solution(object):
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        def isSame(x, y):
            if not x and not y:
                return True
            if not x or not y:
                return False
            return x.val == y.val and \
                   isSame(x.left, y.left) and \
                   isSame(x.right, y.right)

        def preOrderTraverse(s, t):
            return s != None and \
                   (isSame(s, t) or \
                    preOrderTraverse(s.left, t) or \
                    preOrderTraverse(s.right, t))

        return preOrderTraverse(s, t)

Solution from kamyu104/LeetCode-Solutions · MIT