Flatten Binary Tree to Linked List

Problem: Flatten Binary Tree to a Linked List

From a backtracking aspect, we can see that flatten a binary tree at a node means connect mark its flatted left subtree as right child and its flatted right subtree as left subtree's child. Thus we implement a recursive function return flatten list head and tail at one node.

Code in Python:

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        def flat(root):
            if not root:
                return None, None
            head, tail = root, root
            lhead, ltail = flat(root.left)
            rhead, rtail = flat(root.right)
            if lhead:
                tail.right = lhead
                tail = ltail
            if rhead:
                tail.right = rhead
                tail = rtail
            head.left = None
            return head, tail
    flat(root)