## ้ข็ฎๆ่ฟฐ

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

## ไปฃ็ 

### Approach #1 Recursion

Time Complexity && Space Complexity: O(N)

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

1
/ \
2   5
\   \
3   6
\
4

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

### Approach #1 Recursion

``````class Solution {
public void flatten(TreeNode root) {
if (root == null)    return;
if (root.left != null)    flatten(root.left);
if (root.right != null) flatten(root.right);
TreeNode tmp = root.right;
root.right = root.left;
root.left = null;
while (root.right != null) {
root = root.right;
}
root.right = tmp;
}
}``````

### Approach #2 Iteration

``````class Solution {
public void flatten(TreeNode root) {
helper(root);
}

public TreeNode helper(TreeNode node) {
if (node == null)        return null;

if (node.left == null && node.right == null) {
return node;
}

TreeNode leftTail = helper(node.left);
TreeNode rightTail = helper(node.right);

if (leftTail != null) {
leftTail.right = node.right;
node.right = node.left;
node.left = null;
}

return rightTail == null ? leftTail : rightTail;
}
}``````

### Approach #3 O(1) Iteration

``````class Solution {
public void flatten(TreeNode root) {
if (root == null)    return;

TreeNode node = root;

while (node != null) {
if (node.left != null) {
TreeNode rightmost = node.left;
while (rightmost.right != null) {
rightmost = rightmost.right;
}

rightmost.right = node.right;
node.right = node.left;
node.left = null;
} /* end if node.left != null */

node = node.right;
}
}
}``````

### Approach #2 Iterative + Stack

Time Complexity & Space Complexity: O(N)

``````class Solution {
public void flatten(TreeNode root) {
if (root == null)        return;
int START = 1, END = 2;

TreeNode tailNode = null;
Stack<Pair<TreeNode, Integer>> stack = new Stack<Pair<TreeNode, Integer>>();
stack.push(new Pair<TreeNode, Integer>(root, START));

while (!stack.isEmpty()) {
Pair<TreeNode, Integer> nodeData = stack.pop();
TreeNode currentNode = nodeData.getKey();
int recursionState = nodeData.getValue();

if (currentNode.left == null && currentNode.right == null) {
tailNode = currentNode;
continue;
}

if (recursionState = START) {
if (currentNode.left != null) {
stack.push(new Pair<TreeNode, Integer>(currentNode, END));
stack.push(new Pair<TreeNode, Integer>(currentNode.left, START));
} else if (currentNode.right != null) {
stack.push(new Pair<TreeNode, Integer>(currentNode.right, START));
}
} else {
TreeNode rightNode = currentNode.right;
if (tailNode != null) {
tailNode.right = currentNode.right;
currentNode.right = currentNode.left;
currentNode.left = null;
rightNode = tailNode.right;
}

if (rightNode != null) {
stack.push(new Pair<TreeNode, Integer>(rightNode, START));
}
}
}
}
}``````

Last updated