# LeetCode Flatten Binary Tree to Linked List

LeetCode 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

click to show hints.

Hints:If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

1
/
2
/ \
3   4
\
5
\
6

1
\
2
/ \
3   4
\
5
\
6

class Solution2 {
public:
void dfs(TreeNode* par, TreeNode* cur) {
if (cur == NULL)return;
if(par){
if (cur == par->right) {
if (par->left) {
TreeNode* tmp = par->left;
while (tmp->right)tmp = tmp->right;
tmp->right = cur;
par->right = NULL;
}
}
else {
par->right = cur;
par->left = NULL;
}
}
if (cur->right)dfs(cur, cur->right);
if (cur->left)dfs(cur, cur->left);
}
void flatten(TreeNode* root) {
dfs(NULL, root);
}
};

1
/    \
2     5
\       \
3      6 <- rightTail
\
4  <- leftTail

leftTail->right = root->right;
root->right = root->left;
root->left = NULL;

class Solution {
public:
TreeNode* dfs(TreeNode* root) {
if (!root)return NULL;
TreeNode* leftTail = dfs(root->left);
TreeNode* rightTail = dfs(root->right);
if (root->left) {
leftTail->right = root->right;
root->right = root->left;
root->left = NULL;
}
if (rightTail)return rightTail;
if (leftTail)return leftTail;
return root;
}
void flatten(TreeNode* root) {
dfs(root);
}
};