Python solution with head and tail


  • 0
    G
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        self.flatten_tail(root)
        
    def flatten_tail(self, root):
        # return head, tail
        if not root:
            return None, None
        
        left_head, left_tail = self.flatten_tail(root.left)
        right_head, right_tail = self.flatten_tail(root.right)
        
        if not left_head and not right_head:
            return root, root
        elif left_head and not right_head:
            root.left = None
            root.right = left_head
            return root, left_tail
        elif not left_head and right_head:
            return root, right_tail
        else:
            root.right = left_head
            root.left = None
            left_tail.right = right_head
            return root, right_tail

Log in to reply
 

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