# 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
# Solution
Approach 1: recursive solution. Assume that root's left and right subtree are already flattened, we need to hook up the right subtree to left's last node. Therefore we need a helper that returns the last node after flattening.
Approach 2: iterative solution. Keep putting the right subtree under the rightmost leaf in left subtree, then set the left subtree to be the right subtree.
Approach 3: Preorder simulation. For example, iterative solution using stack -- similar to stack based solution for Binary Tree Preorder Traversal, we push right subtree then left subtree onto the stack.
Approach 4: Reverse-postorder simulation.
Approach 5: Inorder simulation.
# Code (Python)
Approach 1:
def flatten(self, root):
# recursive solution
if not root:
return
self._helper(root)
def _helper(self, node):
# this helper assumes node is not None, and it flattens and returns the last non-None node
if not node.left and not node.right:
return node
elif not node.left:
return self._helper(node.right)
elif not node.right:
returned_node = self._helper(node.left)
node.right = node.left
node.left = None
return returned_node
else:
left_last = self._helper(node.left)
right_last = self._helper(node.right)
left_last.right = node.right
node.right = node.left
node.left = None
return right_last
Approach 2:
def flatten(self, root):
if not root:
return
node = root
while node:
if node.left:
current = node.left
while current.right:
current = current.right
current.right = node.right
node.right = node.left
node.left = None
node = node.right
Approach 3:
def flatten(self, root):
# iterative -- stack based preorder traversal
if not root:
return
prev_node = None
stack = [root]
while stack:
node = stack.pop()
if prev_node:
prev_node.right = node
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
node.left = None
prev_node = node
Approach 4: can also connect things without using a prev_node:
def flatten(self, root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
# reconnect things after children have been put on stack
node.left = None
node.right = stack[-1] if stack else None
# Code (C++)
Approach 1:
// Recursion.
class Solution {
private:
TreeNode* doFlattenAndReturnRight(TreeNode* root) {
if (root == NULL)
return NULL;
TreeNode *left = root->left;
TreeNode *right = root->right;
TreeNode *leftRight = doFlattenAndReturnRight(root->left);
TreeNode *rightRight = doFlattenAndReturnRight(root->right);
root->left = NULL;
if (left)
{
root->right = left;
leftRight->right = right;
}
if (rightRight)
return rightRight;
if (leftRight)
return leftRight;
return root;
}
public:
void flatten(TreeNode* root) {
doFlattenAndReturnRight(root);
}
};
Approach 2:
// Iteration.
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode *curr = root;
while (curr)
{
TreeNode *leftMostRight = curr->left;
while (leftMostRight && leftMostRight->right)
leftMostRight = leftMostRight->right;
if (leftMostRight)
{
leftMostRight->right = curr->right;
curr->right = curr->left;
curr->left = NULL;
}
curr = curr->right;
}
}
};
Approach 3:
// Preorder simulation.
class Solution {
private:
TreeNode *prev = NULL;
public:
void flatten(TreeNode* root) {
if (root == NULL)
return;
if (prev)
{
prev->right = root;
prev->left = NULL;
}
prev = root;
TreeNode *right = root->right; // need to save the right.
flatten(root->left);
flatten(right);
}
};
Approach 4:
// Reverse-postorder simulation.
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;
}
};
Approach 5:
// Inorder simulation.
class Solution {
private:
TreeNode *prev = NULL;
public:
void flatten(TreeNode* root) {
if (root == NULL)
return;
flatten(root->left);
TreeNode *right = root->right;
if (root->left)
{
prev->right = right; // this must be first.
root->right = root->left;
root->left = NULL;
}
prev = root;
flatten(root->right); // it's the new right (i.e., root->right).
}
};