Leetcode 114 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 1: Pre-order DFS

 public class Solution {  
   TreeNode pre=null;  
   public void flatten(TreeNode root) {  
     if (root==null) return;  
     TreeNode left=root.left;//x can be change, record the left and right  
     TreeNode right=root.right;  
     if (pre!=null) {  
       pre.left=null;  
       pre.right=root;  
     }  
     pre=root;  
     flatten(left);  
     flatten(right);  
   }  
 }  

Solution 2: Pre-order DFS, iterative

 public class Solution {  
   public void flatten(TreeNode root) {  
     Deque<TreeNode> stack=new LinkedList<>();  
     Queue<TreeNode> qu=new LinkedList<>();  
     TreeNode x=root;  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         stack.push(x);  
         qu.offer(x);  
         x=x.left;  
       }  
       else {  
         x=stack.pop();  
         x=x.right;  
       }  
     }  
     while (!qu.isEmpty()) {  
       x=qu.poll();  
       x.left=null;  
       x.right=qu.isEmpty()?null:qu.peek();  
     }  
   }  
 }