###### tags: `Leetcode` `medium` `tree` `python` `Top 100 Liked Questions`

# 114. Flatten Binary Tree to Linked List

## [題目連結:] https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

## 題目:
Given the ```root``` of a binary tree, flatten the tree into a "linked list":

* The "linked list" should use the same ```TreeNode``` class where the ```right``` child pointer points to the next node in the list and the ```left``` child pointer is always ```null```.
* The "linked list" should be in the same order as a **pre-order traversal** of the binary tree.

#### [圖片來源:] https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

## 解題想法:
* 一路往左去search
* 當前root
* 若有左子root.left:
* 將root.right全移到root.left.right
* 將root.right=root.left
* root.left=None
* root=root.right 繼續loop
* 流程如下:

ex: root=1
            1
    2           5
3       4           6

想法: 一路往左search 
cur=root.left :2
while判斷是否有右子
if 有 cur=cur.right : 4
將目前root的右子全搬去: 5,6搬到4
            1
    2
3       4
            5
                6

並將root.right指向root.left
root.left=None

        1
            2  
        3        4
                    5
                        6
root=root.right 2
.
.
.
重複下去~

## Python: (Sol1)

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        tmp = root
        while tmp:
            if tmp.left:
                cur = tmp.left
                #移動找cur的右子
                while cur.right:
                    cur=cur.right
                #重新連結
                #將tmp的右邊全部移到cur的右邊
                cur.right=tmp.right
                #原本tmp的右指向左，並將左=None
                tmp.right=tmp.left
                tmp.left=None
            tmp=tmp.right
            
root = TreeNode(1)
root.insertLeft(2)
root.insertRight(5)
root.left.insertLeft(3)
root.left.insertRight(4)
root.right.insertRight(6)
root.printTree()
result = Solution()
ans = result.flatten(root)
root.printTree()

## Python: (Sol2)
* 利用pre-order性質: (中)左右
* self.pre紀錄上一點
* 中: 將當前node都更改為pre.right
* 左: Recursive左子
* 右: Recursive右子
* 因為是in-place的改root.right，在dfs回來之後已經不是原來的root.right，因此要先事前拷貝一份。

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        self.pre=None
        self.dfs(root)

    def dfs(self,root):
        if not root:
            return 
        if self.pre!=None:
            self.pre.right=root
            self.pre.left=None
        self.pre=root
        tmp = root.right
        #一路往左去走
        self.dfs(root.left)
        #要用紀錄當前root.right的tmp!!!!
        self.dfs(tmp) #原 root.right 回到此處時已經被修改