Recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
TreeNode left = root.left;
root.left = null;
TreeNode right = root.right;
if (left != null) {
flatten(left);
root.right = left;
TreeNode rightmost = left;
while (rightmost.right != null) {
rightmost = rightmost.right;
}
rightmost.right = right;
}
flatten(right);
}
}
|
Recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
flatten(root.left);
flatten(root.right);
TreeNode leftRoot = root.left;
TreeNode rightRoot = root.right;
root.left = null;
root.right = leftRoot;
TreeNode curr = root;
while (curr.right != null) {
curr = curr.right;
}
curr.right = rightRoot;
}
}
|
Iterate
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public void flatten(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
if (curr.left != null) {
TreeNode leftRoot = curr.left;
curr.left = null;
TreeNode rightRoot = curr.right;
curr.right = leftRoot;
TreeNode tmp = leftRoot;
while (tmp.right != null) {
tmp = tmp.right;
}
tmp.right = rightRoot;
}
curr = curr.right;
}
}
}
|
Iterate
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public void flatten(TreeNode root) {
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
if (root != null) {
stack.push(root);
}
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (pre != null) {
pre.right = node;
pre.left = null;
}
pre = node;
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
}
|
References
114. Flatten Binary Tree to Linked List