Description
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:1
2
3
4
5 1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:1
2
3
4
5
6
7
8
9
10
111
\
2
\
3
\
4
\
5
\
6
Solution
Solution 1:
Just Post traversal, the best1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode pre = null;
public void flatten(TreeNode root) {
if (root == null) return;
flatten(root.right);
flatten(root.left);
root.right = pre;
root.left = null;
pre = root;
}
}
Solution 2:
Used stack, the idea could be used in other problems.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/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void flatten(TreeNode root) {
Stack<TreeNode> st = new Stack<>();
while (root != null || !st.isEmpty()){
if (root.right != null) st.push(root.right);
if (root.left != null){
root.right = root.left;
root.left = null;
}
else if (!st.isEmpty()){
root.right = st.pop();
}
root = root.right;
}
}
}