Python Accepted Solution


  • 1
    P
    class Solution:
        # @param p, a tree node
        # @param q, a tree node
        # @return a boolean
        def isSameTree(self, p, q):
            if p == None and q == None:
                return True
            elif p and q :
                return p.val == q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
            else :
                return False
    

    what's the complexity of this solution?


  • 0
    S

    Starting from the root we have recursion stack as follows:
    O(1) + O(2) + O(4) .. so forth for (1 + log N) times

    However, considering no reduction in input size. I would estimate O(N)

    We would need data with various input sizes to verify this claim via time versus input graph.


  • 0
    S
    This post is deleted!

  • 5
    L

    [AC 85ms] Once find two sub-trees not equal, return False before enter next recursion.

    class Solution:
        # @param p, a tree node
        # @param q, a tree node
        # @return a boolean
        def isSameTree(self, p, q):
            if p == None and q == None:
                return True
            elif p == None or q == None:
                return False
            elif p.val != q.val:
                return False
                
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

  • 0
    P

    I consider the time complexity is O(N) since the algorithm goes through each nodes of the tree.

    {

    class Solution:
        def isSameTree(self, p, q):
        
            if p == None and q == None:
                return True
            elif (p != None and q != None):
                if p.val != q.val:
                    return False    
                if self.isSameTree(p.left, q.left) == False:
                    return False
                else:
                    return self.isSameTree(p.right, q.right)
            else:
                return False
    

    }


Log in to reply
 

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