Flatten Binary Tree to Linked List -- Leetcode

Question:

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

Answer:
Method 1: Recursive 1!

public class Solution {
    public void flatten(TreeNode root) {
        if(root == null)return;
        DFS(root);
        return;
    }
 
    public TreeNode DFS(TreeNode root){
        if(root == null)return null;
        TreeNode right = root.right;
        TreeNode left = root.left;
        TreeNode ret = root;
     
        if(left != null){
            root.right = root.left;
            root.left = null;
            TreeNode leftLastNode = DFS(left);
            ret = leftLastNode;
            leftLastNode.right = right;
            leftLastNode.left = null;
        }
        if(right!=null){
            TreeNode rightLastNode = DFS(right);
            ret = rightLastNode;
        }
        return ret;
    }
}

Recursive 2!
public class Solution {
    public void flatten(TreeNode root) {
        if(root == null)return;
        DFS(root);
        return;
    }
   
    public void DFS(TreeNode root){
        if(root == null)return;
        TreeNode left = root.left;
        TreeNode right = root.right;
     
        DFS(left);
        DFS(right);
       
        if(left != null){
            root.right = left;
            root.left = null;
            TreeNode p = left;
            while(p.right != null){
                p = p.right;
            }
            p.right = right;
            p.left = null;
        }
        return;
    }
}


Method 2: Iterative O(N) time and O(1) space! 

public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            return;
        }
        while (root != null) {
            if (root.left == null) {
                root = root.right;
                continue;
            }
            TreeNode left = root.left;
            while (left.right != null) {
                left = left.right;
            }
            left.right = root.right;
            root.right = root.left;
            root.left = null;
            root = root.right;
        }
    }

Follow up: Convert to inorder double linkedlist!

//Inorder Double LL!

    public void convertToDoubleLinkedList(TreeNode root) {

        if (root == null) {

            return;

        }

        

        if (root.left != null) {

            TreeNode left = root.left;

            convertToDoubleLinkedList(left);

            //find end node of left subtree!

            while (left.right != null) {

                left = left.right;

            }

            //inorder!

            left.right = root;

            root.left = left;

        }

        

        if (root.right != null) {

            TreeNode right = root.right;

            convertToDoubleLinkedList(right);

            while (right.left != null) {

                right = right.left;

            }

            right.left = root;

            root.right = right;

        }

    }