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

# 114 Flatten Binary Tree to Linked List

## 114. Flatten Binary Tree to Linked List

## 1. 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
```

## 2. Implementation

**(1) Morris Tree Traversal**

```java
class Solution {
    public void flatten(TreeNode root) {
        TreeNode curNode = root, preNode = root;

        while (curNode != null) {
            if (curNode.left == null) {
                curNode = curNode.right;
            }
            else {
                preNode = curNode.left;
                while (preNode.right != null) {
                    preNode = preNode.right;
                }
                preNode.right = curNode.right;
                curNode.right = curNode.left;
                curNode.left = null;
                curNode = curNode.right;
            }
        }
    }
}
```

**(2) DFS recursion**

```java
public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        TreeNode rightSubTree = root.right;
        root.right = root.left;
        root.left = null;

        TreeNode curNode = root;
        while (curNode.right != null) {
            curNode = curNode.right;
        }
        curNode.right = rightSubTree;

        flatten(root.right);
    }
```

**(3) DFS iteration**

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

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode curNode = stack.pop();

            if (curNode.right != null) {
                stack.push(curNode.right);
            }

            if (curNode.left != null) {
                stack.push(curNode.left);
            }

            if (!stack.isEmpty()) {
                curNode.right = stack.peek();
            }
            curNode.left = null;
        }
    }
}
```

## 3. Time & Space Complexity

Morris Tree Traversal: 时间复杂度O(n), 空间复杂度O(1)

DFS recursion: 时间复杂度O(n), 空间复杂度O(n)

DFS iteration: 时间复杂度O(n), 空间复杂度(n)