114. 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

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)

Information

  • Created: 2020-01-11 16:49:34

  • Last Motified: 2020-01-11 16:49:34

  • Tags: Tree, Depth-first Search