Python solution with detailed explanation


  • 0
    G

    Subtree of Another Tree https://leetcode.com/problems/subtree-of-another-tree/#/description

    Serialize and Search O(M+N)

    • Serialize s and t using their preorder traversal.
    • Be careful to include left and right child of leaves.
    • Corner case: [12], [2]. This will resolve to "12,#,#" and "2,#,#". The latter is a substring of the former but [2] is not a subtree of [12].
    • Disambiguate by serializing s and t as: "(12)(#)(#)" and "(2)(#)(#)".
    • Then test whether serialization of t is a substring of s.
    • Substring match using KMP is O(M+N). Space used is O(M+N).
    class Solution(object):
        def serialize(self, root, arr):
            if root is None:
                arr.append("#")
            else:
                arr.append("\(%s\)"%(root.val))
                self.serialize(root.left, arr)
                self.serialize(root.right, arr)            
            return
    
        def isSubtree(self, s, t):
            """
            :type s: TreeNode
            :type t: TreeNode
            :rtype: bool
            """
            s_ser, t_ser = [], []
            self.serialize(s, s_ser)
            self.serialize(t, t_ser)
            return "".join(t_ser) in "".join(s_ser)
    

    Preorder Traversal O(MN)

    • We need to test every node in s as a potential candidate for the root of a subtree which is the same as t.
    • Traverse the tree in pre-order.
    • For each node in the traversal, test if the node can be the root.
    • Time complexity: O(MN). Space O(M+N)
    class Solution(object):
        def equals(self, s,t):
            if s is None and t is None:
                return True
            elif s is not None and t is not None:
                return (s.val == t.val) and self.equals(s.left, t.left) and self.equals(s.right, t.right)
            else:
                return False
    
        def isSubtree(self, s, t):
            """
            :type s: TreeNode
            :type t: TreeNode
            :rtype: bool
            """
            if self.equals(s,t):
                return True
            elif s is None:
                return False
            else:
                return self.isSubtree(s.left,t) or self.isSubtree(s.right,t
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.