My accepted non recursive solution in python based on level order traverse


  • 0
    L
    class Solution:
    # @param root, a tree node
    # @return nothing
    def connect(self, root):
        if not root:
            return None
        tmpLeft,queue=root,[]
        if tmpLeft.left and tmpLeft.right:
            queue.append(tmpLeft.left)
            queue.append(tmpLeft.right)
        k,label,range=1,0,1
        # use a queue to perform level order traverse
        while queue:
            tmpRight=queue.pop(0)
            if tmpRight.left and tmpRight.right:
                    queue.append(tmpRight.left)
                    queue.append(tmpRight.right)
            if k<label+range: # the combination of k label and range to determine whether the current note is located at the right edge
                tmpLeft.next=tmpRight
            else:
                tmpLeft.next=None
                label+=range
                # the number of nodes is doubled compared the number of nodes of previous level
                range+=range
            tmpLeft=tmpRight   
            k+=1
        tmpLeft.next=None
    

    The code is based on the level order traverse. Any comments would be appreciated!


  • 0
    X

    The question asked for constant extra space. I'm afraid as long as you use a queue, the space complexity is not constant anymore.


  • 0
    S

    Would you mind sharing a solution that uses constant space. Recursion uses a stack and I wonder how this can be otherwise resolved. I am afraid if the question is wrongly quoted.


Log in to reply
 

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