why tle?


  • 0
    T

    class Solution(object):
    def isSubtree(self, s, t):

        def helper(ss,tt):
            
            if ss is None and tt is None:
                return True
            
            if ss is None or tt is None:
                return False
            
            
            if ss.val == tt.val and helper(ss.left, tt.left) and helper(ss.right, tt.right):
                return True
            
            return helper(ss.left, t) or helper(ss.right, t)
                
        return helper(s,t)
    

    in principle, this should be fine, but why time out


  • 0

    I think your solution is brute force.


  • 0
    T

    your comments are correct, but I can not figure out why another brutal force method can pass, but mine can't

    class Solution(object):

    def isSubtree(self, s, t):
        if t and not s:
            return False
        if self.isSameTree(s, t):
            return True
        else:
            return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
    
    def isSameTree(self, s, t):
        if not t:
            return not s
        else:
            if not s:
                return False
            else:
                return t.val == s.val and self.isSameTree(t.left, s.left) \
                    and self.isSameTree(t.right, s.right)

  • 0

    Your first solution will execute helper(ss.left, tt.left), where tt.left is actually not the t. Your second solution is much better, since it only check every subtree with t, not with any subtree of t.


  • 0
    T

    @fallcreek

    I see the problem. Thanks


Log in to reply
 

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