[LeetCode] 114. Flatten Binary Tree to Linked List

Problem : https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Flatten left tree and right tree.  Append flattened right tree to flatten left tree.Then attach flattened left tree to current root's right child. Finally set current root's left child as None.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        
        def helper(node):
            """
            Flatten tree and return the (head, tail) of the flattened tree
            """
            if not node:
                return (None, None)
            # has both left and right children
            if node.left and node.right:
                lh, lt = helper(node.left)
                rh, rt = helper(node.right)
                
                node.right = lh
                node.left = None
              
                lt.right = rh
               
                return (node, rt)
            
            # only has left child
            if node.left:
                lh, lt = helper(node.left)
                
                node.right = lh
                node.left = None
             
                return (node, lt)
            
            # only has right child
            if node.right:
                rh, rt = helper(node.right)
                
                node.right = rh
                node.left = None
               
                return (node, rt)
            
            # no left or right child
            return (node, node)
        
        return helper(root)[0]