Problem:
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
Solution: We can solve this problem recursively by doing a in-order traversal of the tree.
Implementation:(Recursion)
public class CrazyForCode {
public void flatten(TreeNode root) {
getFlatten(root);
}
public void getFlatten(TreeNode root){
if(root ==null){
return;
}
TreeNode left = root.left;
TreeNode right = root.right;
root.left=null;
getFlatten(left);
getFlatten(right);
root.right=left;
TreeNode current = root;
while(current.right !=null) current = current.right;
current.right =right;
}
}
Non-Recursion, No Stack
We can also solve the problem even without a stack:
Each time when we prune a right subtree, we use while-loop to find the right-most leaf of the current left subtree, and append the subtree there.
public void flatten(TreeNode root) {
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
if (cur.right != null) { // if we need to prune a right subtree
TreeNode next = cur.left;
while (next.right != null) next = next.right;
next.right = cur.right;
}
cur.right = cur.left;
cur.left = null;
}
cur = cur.right;
}
}
We visit each node at most twice (one for flattening and maybe one for looking for rightmost leaf) and then for each node, cut the right tree and append it to its rightmost node. Overall, we access each node constant time. So the total running time is O(n) with O(1) space.
