'''
Description: 
Autor: Au3C2
Date: 2021-03-23 19:50:04
LastEditors: Au3C2
LastEditTime: 2021-03-24 15:14:39
'''
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return
        self.nodelist = list()
        
        def dfs(root):
            if not root: 
                return
            self.nodelist.append(root)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        pre = root
        pre.left = None
        
        for node in self.nodelist[1:]:
            node.left = None
            pre.right = node
            pre = node
        return root

# 树，简单。一点也不简单，辅助空间解法 ↑
# https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

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

        self.flatten(root.left)
        self.flatten(root.right)

        root.left, root.right = root.right, root.left

        most_right = root
        while most_right.right:
            most_right = most_right.right

        most_right.right = root.left
        root.left = None

# ↑ 递归解法