> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/04-20-2022-114.-flatten-binary-tree-to-linked-list.md).

# 04/20/2022 114. Flatten Binary Tree to Linked List

Method: Use divide and conquer. We use preorder and first traverse the sub left tree and get the leftLast node and then traverse the sub right tree and get the rightLast node. Then if the leftLast node is not null, we should attach root.right to the leftLast node's right. Then we need to return the rightLast node if it is not null for next link, otherwise we will return the leftLast node.

Time O(N)

Space O(N)

```
// Some code
class Solution {
    public void flatten(TreeNode root) {
        dfs(root);    
    }
    
    private TreeNode dfs(TreeNode root){
        if (root == null) return null;
        //if (root.left == null && root.right == null) return root;
        
        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;
    }
  
}
```