# 114. Flatten Binary Tree to Linked List(M)

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.

&#x20;

**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]
```

&#x20;

**Constraints:**

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

&#x20;

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

### Solution 1:

我们尝试给出这个函数的定义：

**给 `flatten` 函数输入一个节点 `root`，那么以 `root` 为根的二叉树就会被拉平为一条链表**。

我们再梳理一下，如何按题目要求把一棵树拉平成一条链表？很简单，以下流程：

1、将 `root` 的左子树和右子树拉平。

2、将 `root` 的右子树接到左子树下方，然后将整个左子树作为右子树。

[![](https://labuladong.github.io/algo/images/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%B3%BB%E5%88%97/2.jpeg)](https://labuladong.github.io/algo/images/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%B3%BB%E5%88%97/2.jpeg)

上面三步看起来最难的应该是第一步对吧，如何把 `root` 的左右子树拉平？其实很简单，按照 `flatten` 函数的定义，对 `root` 的左右子树递归调用 `flatten` 函数即可：

```java
// 定义：将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
    // base case
    if (root == null) return;
    
    flatten(root.left);
    flatten(root.right);

    /**** 后序遍历位置 ****/
    // 1、左右子树已经被拉平成一条链表
    TreeNode left = root.left;
    TreeNode right = root.right;
    
    // 2、将左子树作为右子树
    root.left = null;
    root.right = left;

    // 3、将原先的右子树接到当前右子树的末端
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
}
```

```
// 3、将原先的右子树接到当前右子树的末端
   TreeNode p = root;
   while (p.right != null) {
       p = p.right;
   }
```

**这段就是让原右子树接到原左子树的末尾**

[![](https://camo.githubusercontent.com/6927c507572d675aeb861a146b8bc1d1cca18166d38f237b819052e595530298/68747470733a2f2f6c6162756c61646f6e672e67697465652e696f2f616c676f2f696d616765732f2565342562612538632565352538662538392565362561302539312565372562332562622565352538382539372f322e6a706567)](https://camo.githubusercontent.com/6927c507572d675aeb861a146b8bc1d1cca18166d38f237b819052e595530298/68747470733a2f2f6c6162756c61646f6e672e67697465652e696f2f616c676f2f696d616765732f2565342562612538632565352538662538392565362561302539312565372562332562622565352538382539372f322e6a706567)

* 具体到这张图的话, 也就是让`5`接到`4`后面
* 如果**不用**`while`循环, 则`5`会直接接到`2`的后面, 这样点话`3`和`4`就丢失

你看，这就是递归的魅力，你说 `flatten` 函数是怎么把左右子树拉平的？说不清楚，但是只要知道 `flatten` 的定义如此，相信这个定义，让 `root` 做它该做的事情，然后 `flatten` 函数就会按照定义工作。另外注意递归框架是后序遍历，因为我们要先拉平左右子树才能进行后续操作。

### Solution 2: (Non-recursive pre-order traversal)

<https://www.jiuzhang.com/solution/flatten-binary-tree-to-linked-list/>

```
{
Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.empty()) {
        TreeNode node = stack.pop();
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
        
        // connect 
        node.left = null;
        if (stack.empty()) {
            node.right = null;
        } else {
            node.right = stack.peek();
        }
    }
```

### Other Solution:

<https://www.jiuzhang.com/solution/flatten-binary-tree-to-linked-list/>
