114.Flatten Binary Tree to Linked List

In [2]:

from binarytree import Node, build

114. Flatten Binary Tree to Linked List

2 step solution

1. [cur, cur.left, cur.right] order traversal to store the right linked list.
2. flatten given tree from root by using the stored list.

Let $

V

$ be $n$, the time complexity is $O(n)$

In [3]:

class Solution:
    def flatten(self, root: Node) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        order = []
        def func(cur:Node):
            if not cur:
                return
            order.append(cur)
            func(cur.left)
            func(cur.right)
        func(root)
        now = order[0]
        for x in order[1:]:
            now.right = x
            now.left = None
            now = now.right
sol = Solution()

In [6]:

null = None
A = [1,2,5,3,4,null,6]
root = build(A)
root.pprint()
sol.flatten(root)
root.pprint()

    __1
   /   \
  2     5
 / \     \
3   4     6


1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6