Recursive and non-recursive solutions in Python


  • 2
    L

    Recursive one:

      class Solution:
        # @param root, a tree node
        # @return a boolean
        def isSymmetric(self, root):
            # a new recursive function to check if two tree are symetric
            def isMirror(root1,root2):
                    # they all could be Null to be symetric
                if not root1 and not root2:
                    return True
                    # if they are not Null, they must carry the same value
                elif (root1 and root2) and root1.val==root2.val:
                    # recursively call itself
                    return isMirror(root1.left,root2.right) and isMirror(root1.right, root2.left)
                else:
                    return False
            if not root:
                return True
            return isMirror(root.left, root.right)
    

    Non-recursive one:

    class Solution:
        # @param root, a tree node
        # @return a boolean
        def isSymmetric(self, root):
            if not root :
                return True
            queue=[[root.left,root.right]] # use a queue to store nodes. Each element in the queue is a pair of nodes. They are supposed to carry the same value. Ortherwise, the tree is not symetric 
            while queue:
                pair=queue.pop(0)
                if not (pair[0] or pair[1]):
                    # if current pair are empty, do nothing
                    continue
                elif (pair[0] and pair[1]) and pair[0].val==pair[1].val:
                    # if current pair carry the same value, push the their children pairs into the queue
                    queue.append([pair[0].left,pair[1].right]) 
                    queue.append([pair[0].right,pair[1].left])
                else:
                    return False
            # if all pairs pass the evaluation, the tree is symmetric
            return True
    

    Any comments would be appreciated!


  • 0
    S

    Here the "queue" variable is actually a stack.


  • 0
    L

    Hi @sheehan,

    Thanks for the comments. Actually the "queue" is a queue. I use queue.pop(0) to pop the first element in the list instead of the newly appended element. Thus it is a queue.


  • 0
    S

    Sorry, my Implementation use "pop()" not "pop(0)", so I ignored the zero. Use python list as a queue has performance problem that every time pop a element for top of a python list, the runtime would have to move all elements after first one one step ahead. This has a O(n) time complexity.



  • 0
    S

    https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt Here is a summary of most python function time complexity.


  • 0
    L

    Thank you @sheehan for sharing. It's of great help to me. Though pop(0) will have O(n) complexity, all test cases seem to be fine with my submission. Do you mind to share your implementation with stack?


  • 0
    S

    This basically is similar to your code with small optimization

    class Solution:
    
        def check_symmetry(self, node1, node2):
    
            if not node1 and not node2:
                return True
            elif not node1 or not node2:
                return False
        
            return (node1.val == node2.val and 
                self.check_symmetry(node1.left, node2.right) and
                self.check_symmetry(node1.right, node2.left))
    

Log in to reply
 

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