## 114 .Flatten Binary Tree to Linked List

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
``````

Thoughts:

1. Post order (right first); + record prev node
2. d

Code: Recursive

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode prev = null;
public void flatten(TreeNode root) {
if (root == null) return;
flatten(root.right);
flatten(root.left);
root.right = prev;
root.left = null;
prev = root;
}
}
``````

Code: Iterative: Using stack

``````# 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 not root: return
stack = [root]
while stack:
cur = stack.pop()
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
if stack:
cur.right = stack[-1]
cur.left = None
``````

Code: Iterative Traversal C++:

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* top = root;
while(top){
if(top->left){
TreeNode* pre = top->left;
while(pre -> right){
pre = pre->right;
}
pre->right = top -> right;
top -> right = top -> left;
top -> left = NULL;
}

top = top -> right;
}
}
};
``````