【LeetCode】114. Expand binary tree into linked list

1. subject

2. thought

idea ： Want to transform into a left chain subtree , And then again reverse Get the right chain subtree .
The implementation of the first step is a little difficult , But it can also be tried , The second step reverse It's simpler .

3. Code

# 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. """
        #  Change to left chain form 
        self.dfs(root)
        self.reverse(root)
         
    #  Flip binary tree 
    def reverse(self,root):
        if root is None:
            return None
        left_root = self.reverse(root.left)
        right_root = self.reverse(root.right)
        root.left = right_root
        root.right = left_root
        return root

    def dfs(self,root):
        if root is None:
            return 
        
        self.dfs(root.left)
        tmp = root
        while(tmp.left):
            tmp = tmp.left
        
        #  The above one just finds the appropriate root node , But the right subtree has not been （ Sinicization ）
        self.dfs(root.right)
        tmp.left = root.right
        root.right = None #  Set to empty 
        return