Recursive Python Solution


  • 0
    S

    I maintained an invariant here that the left pointer of the list that the code returns back from each recursive call will point to the tail node. Any suggestions for improvement will be greatly appreciated :)

    
    class Solution(object):
        def flatten(self, root):
            if root is None:
                return root
            
            self.convert_tree(root)
            root.left = None
            return
        
        def convert_tree(self, root):
            if root is None:
                return None
            
            if root.left is None and root.right is None:
                root.left = root
                return root
            
            lt = self.convert_tree(root.left)
            rt = self.convert_tree(root.right)
            
            if lt:
                root.right = lt
            else:
                root.right = None
            
            if rt:
                if root.right:
                    lt.left.right = rt
                    root.left = rt.left
                    lt.left = None
                else:
                    root.right = rt
                    root.left = rt.left
                rt.left = None
            else:
                if root.right:
                    root.left = lt.left
                    lt.left = None
                else:
                    root.left = root
    
            return root
    
    

Log in to reply
 

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