LC 114二叉树展开为链表Flatten Binary Tree to Linked List　中等

原地把二叉树按先序顺序展开为右指针串联的链表。

思路 Morris 找前驱：左子树最右节点接原右子树，左子树移到右侧，cur 右移。时间 O(n)，空间 O(1)。

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        cur = root
        while cur:
            if cur.left:
                pre = cur.left
                while pre.right:
                    pre = pre.right
                pre.right = cur.right
                cur.right = cur.left
                cur.left = None
            cur = cur.right