Python solution with detailed explanation


  • 0
    G

    Solution

    Flatten Binary Tree to Linked List https://leetcode.com/problems/flatten-binary-tree-to-linked-list/?tab=Description

    Recursively Post-Order Flattening

    • h,t = flatten_left_subtree
    • h1,t1 = flatten_right_subtree
    • Now merge with the root using cases where h is None, h1 is None or both are None, or both are non None.
    • Make sure to set root.left as None
    class Solution(object):
        def flatten(self, root):
            """
            :type root: TreeNode
            :rtype: void Do not return anything, modify root in-place instead.
            """
            self.flatten_helper(root)
            return
        
        def flatten_helper(self, root):
            if root == None:
                return None, None
            h,t = self.flatten_helper(root.left)
            h1,t1 = self.flatten_helper(root.right)
            
            root.left = None
            if h and h1:
                root.right = h
                t.right = h1
                return root, t1
            elif h == None and h1:
                root.right = h1
                return root, t1
            elif h1 == None and h:
                root.right = h
                return root, t
            else:
                return root, root
    

Log in to reply
 

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