Leetcode: 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

Solution:

This problem just needs to traverse the tree in preorder. We can do that using recursion or a stack, in the case that we want to guarantee constant space a threaded tree as explained in http://jelices.blogspot.com/2013/12/leetcode-binary-tree-preorder-traversal.html.

Stack solution:

public class Solution {
    public void flatten(TreeNode root) {
        if(root==null)
            return;
        Deque stack = new ArrayDeque();
        stack.push(root);
        while(!stack.isEmpty())
        {
            TreeNode pointer = stack.pop();
            if(pointer.right!=null)
                stack.push(pointer.right);
            if(pointer.left!=null)
                stack.push(pointer.left);
            pointer.left = null;
            pointer.right = stack.peek();
        }
    }
}

Recursion Solution:

public class Solution {
    
    TreeNode previous;

    public void flatten(TreeNode root) {
        if(root == null)
            return;
        previous = root;
        TreeNode right = root.right;
        flatten2(root.left);
        flatten2(right);
    }
    
    public void flatten2(TreeNode root)
    {
        if(root == null)
            return;
        previous.left = null;
        previous.right = root;
        previous = root;
        TreeNode right = root.right;
        flatten2(root.left);
        flatten2(right);
    }
}

In-place Solution: This solution is based on cutting the left branch of the tree, pasting it to the right one while we keep the original right as the most-right branch.

public class Solution {
    public void flatten(TreeNode root) {
        while (root != null)
        {
            if (root.left != null)
            {
                TreeNode pre = root.left;
                while (pre.right != null) {pre = pre.right;}
                pre.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }
    }
}