难度: Medium
给你二叉树的根结点 root ，请你将它展开为一个单链表：
TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
示例 1：
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [0] 输出：[0]
提示：
[0, 2000] 内-100 <= Node.val <= 100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
运行时间: 36 ms
内存: 15 MB
# 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
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if root is None:
return
self.flatten(root.left)
self.flatten(root.right)
left = root.left
right = root.right
root.left = None
root.right = left
p = root
while p.right:
p = p.right
p.right = right
该题解采用后序遍历的方式来展开二叉树为链表。具体思路如下： 1. 首先递归处理左子树，将左子树展开为链表。 2. 然后递归处理右子树，将右子树展开为链表。 3. 将原本的左子树作为根节点的右子树，原本的右子树拼接到当前右子树的末端。 4. 将根节点的左子树置为空。
时间复杂度: O(n)
空间复杂度: O(n)
# 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
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if root is None:
return
# 递归处理左子树
self.flatten(root.left)
# 递归处理右子树
self.flatten(root.right)
# 暂存左右子树
left = root.left
right = root.right
# 将左子树作为右子树
root.left = None
root.right = left
# 将原来的右子树接到当前右子树的末端
p = root
while p.right:
p = p.right
p.right = right
使用后序遍历（先处理左子树，再处理右子树，最后处理根节点）可以便于我们在修改树结构时防止丢失对子树的引用。在先序或中序遍历中，如果先处理根节点，然后再展开子树，可能会因修改根节点的右子树指针而丢失原本的右子树引用。而在后序遍历中，由于子树已经被处理和展开，我们可以安全地修改根节点的指针，将处理好的左子树放置到右侧，然后再将原右子树接到新的右子树末端，这样可以有效地保持对所有节点的正确引用，避免数据丢失。
在执行题解的算法过程中，首先将左子树展开并置于根节点的右侧，这保证了根节点后是其左子树的所有节点（按照左子树的先序顺序）。然后，将原右子树拼接到现右子树的末端。由于整个操作开始于根节点后移向左子树，然后左子树的末尾连接到右子树，这自然形成了一个先序遍历的序列（根-左-右）。因此，整个链表自然保持了二叉树的先序遍历顺序。
在算法中，我们首先处理并展开左右子树，然后再进行节点的连接操作。在连接之前，我们已经将左右子树分别保存在变量中，这样即使根节点的左右指针被修改，也不会影响已经保存的树结构。因此，这种方式不会导致原树结构的破坏或数据丢失。实际上，这种方法恰恰是为了保证在修改指针时不丢失任何子树的数据。
确实，对于非常大的二叉树，递归可能导致栈溢出。可以使用迭代方法或显式栈来避免递归。例如，可以使用一个栈来模拟后序遍历的过程。首先将节点按先序遍历的顺序压入栈中（即先压右子节点，后压左子节点）。然后，依次从栈中取出节点，将节点的左子树设为null，右子树连接之前处理的节点。这样反向构建链表，从而不需要使用系统调用栈，减少了栈溢出的风险。