Question:
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
Hint:
If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.
Thinking:
It’s a simple dfs question and it’s pre-order. So we need to make the left-child become right-child of root and make right-child become whole left-child’s right-child.
Solution:
public class Solution {
public void flatten(TreeNode root) {
if (root == null)
return;
dfs(root);
}
public TreeNode dfs(TreeNode root){
if (root.left == null && root.right == null){
return root;
}
TreeNode left = null;
TreeNode right = null;
TreeNode preleft = root.left;
TreeNode preright = root.right;
if (preleft == null){
return dfs(preright);
}
else if(preright == null){
root.left = null;
root.right = preleft;
return dfs(preleft);
}
else{
left = dfs(preleft);
right = dfs(preright);
root.left = null;
root.right = preleft;
left.right = preright;
return right;
}
}
}