# [leetcode] Flatten Binary Tree to Linked List

### Flatten Binary Tree to Linked List

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

tag: tree, depth-first-search

11/16/2015 update

```/**
* 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) {
DFS(root, nullptr);
}
TreeNode * DFS(TreeNode* root, TreeNode * tail){
if(root == nullptr) return tail;
TreeNode * right = DFS(root->right, tail);
TreeNode * left = DFS(root->left, right);
root->left = nullptr;
root->right = left;
return root;
}
};```

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
stack<TreeNode *> s;
void flatten(TreeNode *root) {
if(root == NULL){
return;
}
if(root->left == NULL && root->right == NULL && s.empty() == true){
return;
}
if(root->right != NULL){
s.push(root->right);
}
if(root->left != NULL){
root->right = root->left;
root->left = NULL;
flatten(root->right);
}
else{//root->left == NULL
root->right = s.top();
s.pop();
flatten(root->right);
}
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.