leetcode 114.
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. I learned the solution from here. The point is that build a helper(TreeNode node) function. The helper function will not only flatten node, but also return the tail of the flattened list.
After traverse left and right node, we have leftTail, rightTail and root. We can reconstruct the flatten list easily.
public static void flatten(TreeNode root) {
helper(root);
}
public static TreeNode helper(TreeNode root) {
if (root == null) {
return null;
}
TreeNode leftTail = helper(root.left);
TreeNode rightTail = helper(root.right);
if (leftTail != null) {
leftTail.right = root.right;
root.right = root.left;
root.left = null;
}
if (rightTail != null) {
return rightTail;
}
if (leftTail != null) {
return leftTail;
}
return root;
}
Check my code on github.