114. Flatten Binary Tree to Linked List

Loading...LeetCode

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)的。

postorder

# 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

pre-order 边遍历边展开

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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

inorder

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