> For the complete documentation index, see [llms.txt](https://jaywin.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://jaywin.gitbook.io/leetcode/solutions/0114-flatten-binary-tree-to-linked-list.md).

# 0114. Flatten Binary Tree to Linked List

<https://leetcode.com/problems/flatten-binary-tree-to-linked-list>

## Description

Given the `root` of a binary tree, flatten the tree into a "linked list":

* The "linked list" should use the same `TreeNode` class where the `right` child pointer points to the next node in the list and the `left` child pointer is always `null`.
* The "linked list" should be in the same order as a [**pre-order** **traversal**](https://en.wikipedia.org/wiki/Tree_traversal#Pre-order,_NLR) of the binary tree.

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/01/14/flaten.jpg)

```
**Input:** root = [1,2,5,3,4,null,6]
**Output:** [1,null,2,null,3,null,4,null,5,null,6]
```

**Example 2:**

```
**Input:** root = []
**Output:** []
```

**Example 3:**

```
**Input:** root = [0]
**Output:** [0]
```

**Constraints:**

* The number of nodes in the tree is in the range `[0, 2000]`.
* `-100 <= Node.val <= 100`

**Follow up:** Can you flatten the tree in-place (with `O(1)` extra space)?

## ac

```java
class Solution {
    public void flatten(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) return;

        flatten(root.left);
        flatten(root.right);

        TreeNode tmpR = root.right;
        TreeNode tmpL = root.left;
        root.left = null;
        root.right = tmpL;
        while (tmpL.right != null)  tmpL = tmpL.right;
        tmpL.right = tmpR;

        return;
    }
}
```

## ac2

so smart! you can start from leftmost, but you can start from rightmost as well!

```java
class Solution {
    private TreeNode tmp = null;
    public void flatten(TreeNode root) {
        if (root == null) return;

        flatten(root.right);
        flatten(root.left);

        root.left = null;
        root.right = tmp;
        tmp = root;
    }
}
```