Python solution with detailed explanation

  • 0


    Flatten Binary Tree to Linked List

    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.
        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
                return root, root

Log in to reply

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