题目描述
思路解析
一句话答案：LeetCode 114 二叉树展开为链表的进阶解法是 O(1) 空间的原地指针法：cur 沿右指针逐个处理节点，遇到有左子树的，就沿左子树的右指针走到当前右链末端，把原右子树先接到这个末端节点后面，再把整棵左子树搬到右边、左指针置空。总时间 O(n)、额外空间 O(1)，原地完成。
题目要求的链表长什么样
题目要求把二叉树原地改造成一条只用右指针串起来的单链表：每个节点的 left 都置空，right 指向它在先序遍历（根、左、右）中的下一个节点。题目同时提出两个要求：节点顺序必须严格等于先序，并且要在原来这棵树上直接改指针，不另外新建结构。
先存先序序列再重接，代价在哪里
最直接的做法是先做一遍先序遍历，把节点按顺序存进列表，再从头到尾把 right 逐个接上、left 置空。它正确且好写，但要 O(n) 的额外空间存整个序列；改成递归原地拼接可以省掉列表，递归栈仍要 O(h)。想做到真正的 O(1) 额外空间，就得在不记录任何全局顺序的前提下，靠局部的指针操作一段一段地把树拉直。
关键观察：原右子树该临时接到哪里
回到先序的定义，考察任意一个节点 cur：cur 之后紧跟的是它的整棵左子树，左子树全部走完才轮到原来的右子树。所以把左子树搬到右边之前，必须先给原右子树找一个不破坏顺序的落脚点。做法是沿左子树的右指针一路走到底，找到当前右链的末端节点，把原右子树接到它后面。注意这个末端节点不一定是左子树先序的最后一个节点——左子树里可能还有没展开的左分支——但挂在这里不会出错：先序先左后右，挂上去的整段仍然排在左子树现有全部节点之后；等 cur 往下走到那些更深的左分支时，同样的操作会把这段继续往下推，最终恰好落到完整先序的正确位置。这个「沿右链找接驳点」的手法与 Morris 遍历找前驱是同款技巧。
每一步搬运为什么不丢节点、拼出来恰好是先序
对每个有左子树的节点做三个动作，次序不能乱：先让右链末端节点接管原右子树——先把右子树托付出去，它才不会在下一步被覆盖丢失；再把整棵左子树搬到 right 上；最后把 left 置空。这一轮结束时保证的是三件事：原右子树完好挂在树里没有脱链、左子树整体挪到了 cur 的右侧、cur 本身满足「左空右连」的链表形态——完整的先序顺序并不靠这一轮一次做完，而是 cur 沿 right 前进后，对后面每个还有左子树的节点重复同样的操作，一段一段逐步成形。
两个高频错误：先搬左子树再想起原右子树，此时右指针已被覆盖、整棵右子树永久丢失；搬完忘记把 cur.left 置空，结果不满足「只有右孩子」的链表形态。
为什么总时间还是线性 O(n)
看起来「找最右节点」像嵌套循环，其实不然：每个节点作为某次寻找前驱的途经点，总共只会被走过常数次，所有寻找加起来的步数是线性的，时间 O(n)。空间上只用 cur、pre 两个指针，既无递归也无栈，额外空间 O(1)——这正是它比「先序列表重接」和递归拼接更进一步的地方。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
诀窍在于：对每个有左子树的节点，左子树这一整段在先序里就排在它后面、原右子树前面。所以把左子树最右的节点接上原右子树，再把左子树搬到右边、左指针清空——一段就拉直了。下面逐步看。
准备 · 原始树（9 节点）：先看清原始树：根是 1，有左子树(2…)和右子树(5…)。它的先序遍历是 1 → 2 → 3 → 9 → 4 → 5 → 6 → 7 → 8——这正是展开后链表的节点顺序。接下来分两步：先走一遍先序看清目标顺序，再逐段把树拉直。
先序遍历 · 第 1 个：1：展开的目标顺序，就是这棵树的先序遍历（根 → 左子树 → 右子树）。从根 1 出发，先访问根自己。
先序遍历 · 第 2 个：2：先序的规矩是「根、左、右」，所以走到节点 2。把它接到序列末尾——展开后的链表，节点顺序就得严格按这个先序排。
先序遍历 · 第 3 个：3：先序的规矩是「根、左、右」，所以走到节点 3。把它接到序列末尾——展开后的链表，节点顺序就得严格按这个先序排。
先序遍历 · 第 4 个：9：先序的规矩是「根、左、右」，所以走到节点 9。把它接到序列末尾——展开后的链表，节点顺序就得严格按这个先序排。
先序遍历 · 第 5 个：4：先序的规矩是「根、左、右」，所以走到节点 4。把它接到序列末尾——展开后的链表，节点顺序就得严格按这个先序排。
先序遍历 · 第 6 个：5：先序的规矩是「根、左、右」，所以走到节点 5。把它接到序列末尾——展开后的链表，节点顺序就得严格按这个先序排。
先序遍历 · 第 7 个：6：先序的规矩是「根、左、右」，所以走到节点 6。把它接到序列末尾——展开后的链表，节点顺序就得严格按这个先序排。
先序遍历 · 第 8 个：7：先序的规矩是「根、左、右」，所以走到节点 7。把它接到序列末尾——展开后的链表，节点顺序就得严格按这个先序排。
先序遍历 · 第 9 个：8：先序的规矩是「根、左、右」，所以走到节点 8。把它接到序列末尾——展开后的链表，节点顺序就得严格按这个先序排。
展开 · 节点 1 有左子树：轮到节点 1，它还挂着左子树。先序里，左子树整段要排在 1 之后、原右子树之前。所以先找到左子树最右节点 4(蓝)——它将成为接驳点。
重排完成 · 1 的左子树已右移：三步指针操作：① 把 1 原来的右子树接到 4.right；② 把左子树整段搬到 1.right；③ 1.left 置空。现在 1 只剩右孩子，左子树乖乖排到了它后面——这一段先序就被「拉直」了。
展开 · 节点 2 有左子树：轮到节点 2，它还挂着左子树。先序里，左子树整段要排在 2 之后、原右子树之前。所以先找到左子树最右节点 3(蓝)——它将成为接驳点。
重排完成 · 2 的左子树已右移：三步指针操作：① 把 2 原来的右子树接到 3.right；② 把左子树整段搬到 2.right；③ 2.left 置空。现在 2 只剩右孩子，左子树乖乖排到了它后面——这一段先序就被「拉直」了。
展开 · 节点 3 有左子树：轮到节点 3，它还挂着左子树。先序里，左子树整段要排在 3 之后、原右子树之前。所以先找到左子树最右节点 9(蓝)——它将成为接驳点。
重排完成 · 3 的左子树已右移：三步指针操作：① 把 3 原来的右子树接到 9.right；② 把左子树整段搬到 3.right；③ 3.left 置空。现在 3 只剩右孩子，左子树乖乖排到了它后面——这一段先序就被「拉直」了。
节点 9 无左子树 · 直接前进：节点 9 没有左子树，它本来就只有右孩子，已经在右链上了，不用动。指针顺着右孩子继续往下，去处理 下一个节点 4。
节点 4 无左子树 · 直接前进：节点 4 没有左子树，它本来就只有右孩子，已经在右链上了，不用动。指针顺着右孩子继续往下，去处理 下一个节点 5。
节点 5 无左子树 · 直接前进：节点 5 没有左子树，它本来就只有右孩子，已经在右链上了，不用动。指针顺着右孩子继续往下，去处理 下一个节点 6。
展开 · 节点 6 有左子树：轮到节点 6，它还挂着左子树。先序里，左子树整段要排在 6 之后、原右子树之前。所以先找到左子树最右节点 7(蓝)——它将成为接驳点。
重排完成 · 6 的左子树已右移：三步指针操作：① 把 6 原来的右子树接到 7.right；② 把左子树整段搬到 6.right；③ 6.left 置空。现在 6 只剩右孩子，左子树乖乖排到了它后面——这一段先序就被「拉直」了。
节点 7 无左子树 · 直接前进：节点 7 没有左子树，它本来就只有右孩子，已经在右链上了，不用动。指针顺着右孩子继续往下，去处理 下一个节点 8。
节点 8 无左子树 · 直接前进：节点 8 没有左子树，它本来就只有右孩子，已经在右链上了，不用动。指针顺着右孩子继续往下，去处理 ——到这已是链尾。
答案 · 展开成右斜链表：全部拉直！现在每个节点都只有右孩子，从 1 一路沿右指针垂到 8，顺序 1 → 2 → 3 → 9 → 4 → 5 → 6 → 7 → 8 正好是先序遍历。这就是"二叉树展开为链表"。
参考代码
class Solution { public void flatten(TreeNode root) { TreeNode cur = root; while (cur != null) { if (cur.left != null) { TreeNode pre = cur.left; // 左子树 while (pre.right != null) // 找左子树最右(先序末尾) pre = pre.right; pre.right = cur.right; // 原右子树接到它后面 cur.right = cur.left; // 左子树整段搬到右边 cur.left = null; // 左指针清空 } cur = cur.right; // 沿右脊前进 } }}复杂度
- 时间：O(n)，每节点最多被「沿右脊找最右」访问常数次，总体线性
- 空间：O(1)，只用 cur/pre 两个指针，原地改指针、无递归栈
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
合并二叉树
LeetCode 617 · 简单 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题