 6/22/2017 - 8:23 AM

## 114. Flatten Binary Tree to Linked List

1. Flatten Binary Tree to Linked List
``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
if root == None:
return None
res = []
stack = [root]

while len(stack) != 0:
curNode = stack[-1]
del stack[-1]
res.append(curNode)
if curNode.right:
stack.append(curNode.right)
if curNode.left:
stack.append(curNode.left)

# Note that in preorder, the last node is bound to be leaf node,
# so you don't have to redirect its left and right.
for i in range(len(res)-1):
res[i].left = None
res[i].right = res[i+1]``````

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

For example, Given

``````
1
/ \
2   5
/ \   \
3   4   6
``````

The flattened tree should look like:

``````   1
\
2
\
3
\
4
\
5
\
6
``````