Recursive and non-recursive solutions in python


  • 0
    L

    Recursive one:

    class Solution:
    # @param root, a tree node
    # @return nothing, do it in place
    def flatten(self, root):
        if not root:
            return None
        elif not (root.left or root.right): 
            return root 
        temp=root
        while temp and (temp.left or temp.right):
            if temp.left:
                # flatten the left subtree if exist and return the end node
                tmptail=self.flatten(temp.left) 
                # insert the flattened left subtree into the original tree. Then set the left child as None and update the temp.
                temp.right,temp.left,tmptail.right,temp=temp.left,None,temp.right,tmptail
            else:
                temp=temp.right
        return temp
    

    Non recursive one:

    class Solution:
        # @param root, a tree node
        # @return nothing, do it in place
        def flatten(self, root):
            tmpGreat=root
            while tmpGreat:
                if tmpGreat.left:
                    tmpInner=tmpGreat.left
                    while tmpInner.right:
                        tmpInner=tmpInner.right
                    tmpGreat.left, tmpGreat.right, tmpInner.right= None, tmpGreat.left, tmpGreat.right
                tmpGreat=tmpGreat.right
    

    The code is based on the same algorithm from @zjulyx 's post.

    When executed, the recursive one is 2x faster than its opposite. Any comments would be appreciated!


  • 0
    Y

    In your recursive version, checking temp in the while loop is redundant and cause a lot of confusion. Actually, we need to ensure tmpTail (and hence temp since temp if the return value) can never be none in order for tmpTail.right = xxx works, so no need to check that in the while loop.


Log in to reply
 

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