[LeetCode] Problem 114 - Flatten Binary Tree to Linked List

Posted on | In ,

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
11
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
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
public void flatten(TreeNode root) {
    helper(root);
}

private TreeNode helper(TreeNode root) {
    if (root == null)
        return null;

    TreeNode leftTail = helper(root.left);
    TreeNode rightTail = helper(root.right);

    if (root.left != null) {
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = null;
        leftTail.right = temp;
    }

    if (rightTail != null)
        return rightTail;
    else if (leftTail != null)
        return leftTail;
    else
        return root;
}