Flatten Binary Tree to Linked List

Intuition

Based on the example, the flattened linked list is in the order of pre-order traversal of the tree. So we could do the pre-order traversal and edit last node at the same time to get the result.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.last = TreeNode(None)
        self._helper(root)

    def _helper(self, node: TreeNode) -> None:
        if node is None:
            return
        l, r = node.left, node.right
        self.last.left = None
        self.last.right = node
        self.last = node
        self._helper(l)
        self._helper(r)