Flatten Binary Tree to Linked List

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

click to show hints.

Hints: If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
     public void flatten(TreeNode root) {
        flattern(root);
    }

    public List<TreeNode> flattern(TreeNode root) {
        if (root == null) {
            return Arrays.asList(null, null);
        }

        if (root.left != null) {
            List<TreeNode> nodes = flattern(root.left);

            TreeNode temp = root.right;
            root.right = nodes.get(0);

            if (nodes.get(1) != null) {
                nodes.get(1).right = temp;
            }

            root.left = null;

            if (temp !=null) {
                List<TreeNode> more = flattern(temp);

                return Arrays.asList(root, more.get(1));
            } else {
                return Arrays.asList(root, nodes.get(1));
            }
        } else if (root.right != null){
            List<TreeNode> more1 = flattern(root.right);
            return Arrays.asList(root, more1.get(1));
        } else {
            return Arrays.asList(root, root);
        }
    }
}