Leetcode 114. Flatten Binary Tree to Linked List (Python)

Related Topic

Depth-First-Search. Tree. Postorder-Traversal.

Description

Given a binary tree, flatten it to a linked list in-place.

Sample I/O

For example, given the following tree:

Example 1

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Methodology

This question can be solved by Depth First Search.

In the result, all the nodes’ left node is None and right node is next node based on inorder traversal. We want all node’s connect to it’s next node in order to flatter the tree to a linked list. Here, we can use postorder traversal and switch read left child node first to read right child node first to get same result. The benefit is in each recursion, we can store the current node as the right child node for next node after recusion. This will connect all nodes.

To avoid using class variable, we are going to use stack or list to store the current node.

Code

def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        def dfs(root, tmp):
            if root is None:
                return
            dfs(root.right,tmp)
            dfs(root.left,tmp)
            root.right = tmp.pop()
            root.left = None
            tmp.append(root)
            return root
        return dfs(root, [None])

BigO

We traversal all nodes once so the total time complexity is O(n)