O(1) space Python Solution with explanation


  • 0
    G
        current_node = root
        need_to_assign = '<EMPTY_NODE>'
        next_layer_start = '<EMPTY_NODE>'
    
        
        while True:
            # search for start of next layer
            if next_layer_start == '<EMPTY_NODE>':
                if current_node.left != None:
                    next_layer_start = current_node.left
                elif current_node.right != None:
                    next_layer_start = current_node.right
    
            # try to link the former node and update 'need_to_assign'
            if need_to_assign == '<EMPTY_NODE>':
                if current_node.right != None:
                    need_to_assign = current_node.right
                elif current_node.left != None:
                    need_to_assign = current_node.left
            else:
                if current_node.left != None and current_node.right == None:
                    need_to_assign.next = current_node.left
                    need_to_assign = current_node.left
                elif current_node.left == None and current_node.right != None:
                    need_to_assign.next = current_node.right
                    need_to_assign = current_node.right
                elif current_node.left != None and current_node.right != None:
                    need_to_assign.next = current_node.left
                    need_to_assign = current_node.right
            
            # try to link left child to right child
            if current_node.left != None and current_node.right != None:
                current_node.left.next = current_node.right
                
            # go to next node on the same level or go to next level
            if current_node.next != None:
                current_node = current_node.next
            else:
                if next_layer_start == '<EMPTY_NODE>':
                    break
                current_node = next_layer_start
                need_to_assign = '<EMPTY_NODE>'
                next_layer_start = '<EMPTY_NODE>'

Log in to reply
 

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