Flatten Binary Tree to Linked List

Java

public class Solution {
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    public void flatten(TreeNode root) {
        // write your code here
        dfs(root);
    }
    
    public TreeNode dfs(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        TreeNode leftlast = dfs(root.left);
        TreeNode rightlast = dfs(root.right);
        
        if (leftlast != null) {
            leftlast.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        if (rightlast != null) {
            return rightlast;
        }
        if (leftlast != null) {
            return leftlast;
        }
        
        return root;
    }
}