Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
/ \
2   5
/ \   \
3   4   6


The flattened tree should look like:

1
\
2
\
3
\
4
\
5
\
6


## Solutions

### 1. DFS-迭代

# Time Complexity: O(n)
# Space Complexity: O(n)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if not root:
return None
node = root
stack = [node]
while stack:
cur = stack.pop()
if not cur:
continue
if node != cur:
node.left = None
node.right = cur
node = cur
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
# Runtime: 36 ms, faster than 96.86% of Python3 online submissions for Flatten Binary Tree to Linked List.
# Memory Usage: 13.8 MB, less than 8.70% of Python3 online submissions for Flatten Binary Tree to Linked List.


### 2. DFS-递归

# Time Complexity: O(n)
# Space Complexity: O(n)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def __init__(self):
self.prev = None

def flatten(self, root):
if not root:
return None
self.flatten(root.right)
self.flatten(root.left)

root.right = self.prev
root.left = None
self.prev = root
# Runtime: 48 ms, faster than 23.98% of Python3 online submissions for Flatten Binary Tree to Linked List.
# Memory Usage: 13.8 MB, less than 8.70% of Python3 online submissions for Flatten Binary Tree to Linked List.