二叉树展开为链表
Flatten Binary Tree to Linked List
把二叉树原地展开成一条单链表：顺序为前序遍历，所有 left 置空，连接用 right。
在力扣中练习题目描述
给你二叉树的根结点 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) 额外空间）展开这棵树吗？
解题思路
前序拼接 · 原地
有左子树就把它整体搬到右边，接到原右子树前面
展开后的顺序是前序：根、左子树、右子树。对每个节点，如果它有左子树，左子树展开后的最后一个节点应该接上原来的右子树，然后整条左链移到右边。
具体做法：找到左子树的最右节点 prev（它在前序里是左子树的最后一个）；把 prev->right 接到 cur->right；再把 cur->right 改为 cur->left，并清空 cur->left。
目标是前序顺序：根、左子树、右子树。每个有左孩子的节点都要做一次“摘左接右”。
然后 cur 沿着新的 right 继续。每个节点只处理一次，所有“找最右节点”的遍历加起来是 O(n)，额外空间 O(1)。
节点 5：左子树最右 6 接上原右子树 8；5 的左孩子移到右边并清空左指针。
左子树的最右节点必须先保存，否则接上右子树后它会被覆盖。
自拟树里 5 的左子树最右是 6（不是 4），8 的左子树最右是 7；拼接点必须真的沿 right 走到底。最终链是 5 → 3 → 1 → 2 → 4 → 6 → 8 → 7 → 9。
易错点
- 没保存原来的右子树：直接覆盖 cur->right 会丢掉整段。
- 把 cur->left 直接接到 cur->right，却没接到左子树最右节点：前序顺序错。
- 忘记清空 left：树里仍有左指针，不是单链表。
- 只处理根节点：子树内部的左链没有展开。
前序收集 · 重新接线
先按前序把所有节点收进数组，再统一改指针
写法最稳，但需要 O(n) 数组保存所有节点；主解法用原地拼接把空间降到 O(1)。
先做一次前序遍历，把所有节点按顺序放进 vector。然后从第二个节点开始，依次让前一个节点的 right 指向当前节点，并把前一个节点的 left 置空。
这种方法不需要在树里反复找“最右节点”，逻辑非常直观；代价是 O(n) 额外空间，而且需要额外处理最后一个节点的 right。
如果题目允许额外空间，它比原地版更容易写对；面试若要求原地，就必须用拼接法。
- 1前序遍历收集节点。
- 2依次把相邻节点用 right 连接。
- 3清空每个节点的 left。
- 4最后一个节点的 right 置空。
易错点
- 遍历时修改指针：前序还没走完，右子树入口可能已经丢失。
- 忘记清空最后一个节点的 right：可能留下旧连接。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
root = [5,3,8,1,4,7,9,null,2,null,6]目标是前序顺序：根、左子树、右子树。每个有左孩子的节点都要做一次“摘左接右”。
查看 C++ 代码
延伸阅读
- “把左子树搬到右边”本质上是原地重排前序序列，不需要新建节点。
- 递归版也能做：先展开左右子树，再把左链尾接到右链头；但递归栈是 O(h)。