114. Flatten Binary Tree to Linked List (Medium)
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1 / \ 2 5 / \ \ 3 4 6
The flattened tree should look like:
1 \ 2 \ 3 \ 4 \ 5 \ 6
Solutions
class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
recurse(root);
}
private TreeNode recurse(TreeNode root) {
// return null if reach the end
if (root == null) {
return null;
}
// flatten left branch
TreeNode left = recurse(root.left);
// flatten right branch
TreeNode right = recurse(root.right);
// FIXME Do not forget to unlink to root.left
root.left = null;
if (left != null) {
// append right branch to the end of left branch if left exists
append(left, right);
// link root.right to the head of left branch if left exits.
// if left not exists, do not modify anything.
root.right = left;
}
return root;
}
private void append(TreeNode left, TreeNode right) {
while (left.right != null) {
left = left.right;
}
left.right = right;
}
}