114 Flatten Binary Tree to Linked List

114. Flatten Binary Tree to Linked List

1. Question

Given a binary tree, flatten it to a linked list in-place.
For example, Given
1
1
2
/ \
3
2 5
4
/ \ \
5
3 4 6
Copied!
The flattened tree should look like:
1
1
2
\
3
2
4
\
5
3
6
\
7
4
8
\
9
5
10
\
11
6
Copied!

2. Implementation

(1) Morris Tree Traversal
1
class Solution {
2
public void flatten(TreeNode root) {
3
TreeNode curNode = root, preNode = root;
4
5
while (curNode != null) {
6
if (curNode.left == null) {
7
curNode = curNode.right;
8
}
9
else {
10
preNode = curNode.left;
11
while (preNode.right != null) {
12
preNode = preNode.right;
13
}
14
preNode.right = curNode.right;
15
curNode.right = curNode.left;
16
curNode.left = null;
17
curNode = curNode.right;
18
}
19
}
20
}
21
}
Copied!
(2) DFS recursion
1
public void flatten(TreeNode root) {
2
if (root == null) {
3
return;
4
}
5
6
TreeNode rightSubTree = root.right;
7
root.right = root.left;
8
root.left = null;
9
10
TreeNode curNode = root;
11
while (curNode.right != null) {
12
curNode = curNode.right;
13
}
14
curNode.right = rightSubTree;
15
16
flatten(root.right);
17
}
Copied!
(3) DFS iteration
1
class Solution {
2
public void flatten(TreeNode root) {
3
if (root == null) {
4
return;
5
}
6
7
Stack<TreeNode> stack = new Stack<>();
8
stack.push(root);
9
10
while (!stack.isEmpty()) {
11
TreeNode curNode = stack.pop();
12
13
if (curNode.right != null) {
14
stack.push(curNode.right);
15
}
16
17
if (curNode.left != null) {
18
stack.push(curNode.left);
19
}
20
21
if (!stack.isEmpty()) {
22
curNode.right = stack.peek();
23
}
24
curNode.left = null;
25
}
26
}
27
}
Copied!

3. Time & Space Complexity

Morris Tree Traversal: 时间复杂度O(n), 空间复杂度O(1)
DFS recursion: 时间复杂度O(n), 空间复杂度O(n)
DFS iteration: 时间复杂度O(n), 空间复杂度(n)