Two solutions with python


  • 0
    class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        #solution 1:递归
        '''if not p and not q:return True
        elif not p and q:return False
        elif not q and p:return False
        else:
            if p.val!=q.val:
                return False
            else:
                return(self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right))'''
        #solution 2:非递归
        if p and not q:return False
        elif q and not p:return False
        elif not p and not q:return True
        stack_p,stack_q=[],[]
        stack_p.append(p)
        stack_q.append(q)
        while stack_p and stack_q:
            temp_p,temp_q=stack_p.pop(0),stack_q.pop(0)
            if temp_p.val!=temp_q.val:
                return False
            else:
                if temp_p.left and temp_q.left:
                    stack_p.append(temp_p.left)
                    stack_q.append(temp_q.left)
                if (temp_p.left and not temp_q.left) or (not temp_p.left and  temp_q.left):
                    return False
                if temp_p.right and temp_q.right:
                    stack_p.append(temp_p.right)
                    stack_q.append(temp_q.right)
                if (temp_p.right and not temp_q.right) or (not temp_p.right and  temp_q.right):
                    return False
        return True

Log in to reply
 

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