114. 二叉树展开为链表 (Medium)
专题归类： 05-二叉树 LeetCode 链接： https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你二叉树的根节点 root，请你将它展开为一个单链表：
- 展开后的单链表应该与二叉树 前序遍历 顺序相同。
- 使用节点的
right指针作为链表的next指针，left指针置为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) 额外空间）展开吗？
题目详细分析
- 数据范围含义： 最多 2000 节点，递归深度最多 2000，Python 默认递归深度不够（约 1000），可能需要迭代法或提高递归限制。但一般二叉树不会是链状，实际深度远小于 2000。
- 输入输出特征： 输入根节点，原地修改树，不需要返回（或返回根节点）。修改后的树只有 right 指针有效，left 全部为 None。
- 边界条件： 空树直接返回 None；单节点无需处理。
- 核心约束： 必须按照前序遍历的顺序串联；原地修改（不能新建节点）；left 指针必须置空。
- 隐藏条件： 进阶要求 O(1) 空间——即不能用递归（隐式栈）或额外队列存储遍历结果。
小白版直白理解
就像把一棵圣诞树拆解后平铺在地上——按照「先看树顶→再看左边树枝→最后看右边树枝」的顺序，把每个节点用一根绳子（right 指针）串起来。串好后每个节点的左边（left 指针）不再指向任何东西，只有右边（right 指针）指向下一个节点。
解题思路
思路一：后序遍历 + prev 指针（推荐）
核心思想： 按照 右→左→根 的顺序（后序遍历变体）处理节点。用一个 prev 指针记录上一个处理完的节点。每处理一个节点，就把它的 right 指向 prev，left 置空。
为什么用这个遍历顺序？ 前序遍历的顺序是「根→左→右」。如果按这个顺序正着处理，根节点的右指针需要指向左子树的根，但此时左子树还没处理完。如果我们反过来想——从最后一个节点开始往前串，前序遍历序列的最后一个节点是右子树的最右节点。按「右→左→根」的顺序处理，相当于从后往前构建链表。每处理一个节点，把它链接到已经处理好的「子链表」前面，这样当前节点就成了新的链表头。
def flatten(root):
prev = None # 记录上一个处理完的节点
def dfs(node):
nonlocal prev
if not node:
return
# 后序遍历的变体：右→左→根
dfs(node.right) # 先处理右子树
dfs(node.left) # 再处理左子树
# 当前节点：right 指向 prev，left 置空
node.right = prev
node.left = None
prev = node # 更新 prev 为当前节点
dfs(root)思路二：迭代法（寻找前驱，O(1) 空间）
核心思想： 从根节点开始，如果当前节点有左子树，找到左子树中最右边的节点（前驱节点），将当前节点的右子树接到这个前驱的 right 上，然后把左子树移到右边，左子树置空。然后移动到下一个右节点继续。
为什么这样可行？ 前序遍历的顺序是「根→左→右」。对于当前节点，它的下一个节点应该是左子树的根节点。所以把左子树移到右边，然后把原来的右子树接到左子树的最右节点后面——这样「左」和「右」在链表上就衔接上了。
def flatten(root):
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易错点
- 后序法的遍历顺序不是标准后序： 标准后序是「左→右→根」，这里用的是「右→左→根」。目的是先处理序列末尾的节点，从后往前串联。
- 迭代法找到前驱后，要记得把左子树置空：
cur.left = None很容易忘记。不置空的话树结构没有被完全展开。 - 迭代法循环条件： 循环条件是
cur（不断走 right），而不是cur.right。因为展开过程中 cur.right 会变化。 - 后序法的 prev 指针初始为 None： 这样最后一个处理的节点（前序遍历的第一个节点，即根节点）的 right 会被置为 None，符合要求。
框架提炼
后序变体串联链表模板： 当需要按某种遍历顺序将树串联为链表时，从尾到头反向构建。
prev = None
def dfs(node):
nonlocal prev
if not node: return
dfs(node.right) # 先处理「在序列中更靠后的」子树
dfs(node.left) # 再处理「在序列中更靠前的」子树
node.right = prev # 当前节点的 next 指向已串联好的部分
node.left = None
prev = node # 当前节点成为新的链表头迭代式原地修改树结构模板： 当需要原地将树转换为另一种结构时，使用 while 循环 + 寻找前驱/后继的方式：
cur = root
while cur:
if cur.left:
pre = 左子树的最右节点
pre.right = cur.right # 嫁接右子树
cur.right = cur.left # 左子树移到右边
cur.left = None
cur = cur.right关联题目
- 226-翻转二叉树 — 同样是递归修改树的结构，从翻转扩展到展开是二叉树修改题的进阶。
- 105-从前序与中序遍历构造二叉树 — 前序遍历顺序是本题的核心参考，需要深刻理解前序才能理解展开逻辑。
- 430-扁平化多级双向链表 — 类似思路的链表展开问题，可以对比学习。