# 114. Flatten Binary Tree to Linked List

{% embed url="<https://leetcode.com/problems/flatten-binary-tree-to-linked-list/>" %}

### Postorder (reversed right-first preorder)

看example很像`preorder traversal`，但其实因为要 in-place，所以只能是从叶子节点开始操作，那操作顺序只能是`postorder`或者`inorder`的。

早先想到的思路是借助指针在`postorder`的过程中修改left/right指针，对于每一个节点`cur`执行：

1. 把`cur.right`修改成`pointer`指向的节点（前一个执行操作的节点）
2. 把`cur.left`修改成`None`
3. 把`pointer`指向到`cur`

写完发现`tree`和`linked list`不一样，不支持那种指针操作，类似`pointer = pointer.right`这种命令会无限loop下去。

既然不能用指针，那尝试设置变量来维护这个指向，借助全局变量`prev`做`recursive`，写出来的话其实应该是个`reversed right-first preorder`。

### Pre-order 边遍历边展开

展开为单链表的做法是，维护上一个访问的节点 prev，每次访问一个节点时，令当前访问的节点为 curr，将 prev 的左子节点设为 null 以及将 prev 的右子节点设为 curr，然后将 curr 赋值给 prev，进入下一个节点的访问，直到遍历结束。需要注意的是，初始时 prev 为 null，只有在 prev 不为 null 时才能对 prev 的左右子节点进行更新。

作者：LeetCode-Solution 链接：<https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/er-cha-shu-zhan-kai-wei-lian-biao-by-leetcode-solu/> 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

### Inorder

题目推荐solution里用的是`inorder`解法，不依靠`prev`指针，而是依靠锚定的`left tail`来完成剪接：

1. 找到最左下角的`node`，记录为`left tail`
2. 从找到`left tail`的时刻开始，不断把左子树剪接到右边去，再把原本的右子树接到`left tail`的右边
3. 对原本的右子树也执行一遍算法（它的子树都没被剪接过）

该解法不借助栈来存储node信息，空间复杂度是O(1)的。

{% tabs %}
{% tab title="postorder" %}

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

# obviously it requires preorder traverse.
# we can traverse the whole tree and generate a new list base on the traverse result.
# or, when traversing, the link between nodes shall be adjusted.

# but it asks us  to flatten in-place, we can only do it in the later way.
# and it can not be directly preorder. we need to reverse the iteration
# which means the order shall be 1.right, 2.left, 3.process self
# every time we iterate a node, we store it, then link it to the right of next

class Solution:
    def __init__(self):
        self.prev = None

    def flatten(self, root):
        if not root: return
        self.flatten(root.right)
        self.flatten(root.left)

        root.right = self.prev
        root.left = None
        self.prev = root
```

{% endtab %}

{% tab title="pre-order 边遍历边展开" %}

```python
class Solution:
    def flatten(self, root: TreeNode) -> None:
        if not root:
            return
        
        stack = [root]
        prev = None
        
        while stack:
            curr = stack.pop()
            if prev:
                prev.left = None
                prev.right = curr
            left, right = curr.left, curr.right
            if right:
                stack.append(right)
            if left:
                stack.append(left)
            prev = curr

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/er-cha-shu-zhan-kai-wei-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```

{% endtab %}

{% tab title="inorder" %}

```python
class Solution:
    def flatten(self, root: TreeNode) -> None:
        curr = root
        while curr:
            if curr.left:
                predecessor = nxt = curr.left
                while predecessor.right:
                    predecessor = predecessor.right
                predecessor.right = curr.right
                curr.left = None
                curr.right = nxt
            curr = curr.right

```

{% endtab %}
{% endtabs %}
