Leetcode Link: 114. 二叉树展开为链表 - 力扣（LeetCode） (leetcode-cn.com)
题目
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 None 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
Attention
这里有一个很大的误区是，他提到了先序遍历，不代表就要在先序遍历的位置进行某些操作，具体在哪里进行操作，需要考虑问题究竟是只需要当前节点的信息，还是需要当前节点子树的信息
解法一
思路：递归。将问题分解成子问题，即将一个节点的两个子树都变成往右指的形式(下图)，在合并的时候，脑子里想一下如果输出是先序遍历的顺序对应的合并顺序是怎么样的
对中间的某一个节点来说的是这个意思，开始的时候我总像的是左边的节点都想左指，右边的都向右指，这点困扰了我好久，原来是错的。
在第一个箭头处改变合并的顺序
题解：
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
# 叶子节点跳出, root为None跳出
if not root or (not root.right and not root.left):
return root
left_flattened = self.flatten(root.left)
right_flattened = self.flatten(root.right)
# 把右子树暂存起来
tmp = right_flattened
# 先序的顺序是“中左右”
# 所以可以直接把左子树（左子树目前全部向右指）直接放到当前节点的左子树
root.right = root.left
# 注意一定要断开左子树
root.left = None
# 找到当前右边的叶子，并接上原来的右子树
cur = root
while(cur.right):
cur = cur.right
cur.right = tmp
return root解法二
思路：迭代实现
题解：网友思路
class Solution:
def flatten(self, root: TreeNode) -> None:
# 根节点不为空
while root:
# 左子树不为空
if root.left:
most_right = root.left
# 找到左子树的最右节点
while most_right.right:
most_right = most_right.right
# 左子树最右节点的右子树为根节点的右子树
most_right.right = root.right
# 根节点的左子树置为空，根节点右子树置为根节点的左子树
root.left, root.right = None, root.left
# 循环处理右子树 -> 这是重点把应该，我还没太理解
root = root.right
return None我也不知道我的这个为什么不对，这个in-place究竟是什么意思？是变量名不边还是这个的内存地址不能变？cur=root之后cur的内存地址和root的内存地址一样吗？
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if not root:
return []
stack = []
stack.append(root)
while(len(stack)>0):
cur = stack.pop()
root.right = cur
root.left = None
root = root.right
if cur.right: stack.append(cur.right)
if cur.left: stack.append(cur.left)解法三
思路：
morris 能做吗 todo
题解：