1. 题目理解与核心思路拆解1.1 这道题到底在问什么LeetCode 114“二叉树展开为链表”是一道非常典型的二叉树题目也是面试中经常被拿来考察候选人对递归、指针操作和树结构理解深度的题目。题面看起来很简单给定一棵二叉树把它原地展开成一个单链表展开顺序要符合二叉树的先序遍历结果右指针当作链表的 next 指针左指针一律置空。比如一棵树长这样1 / \ 2 5 / \ \ 3 4 6先序遍历结果是 1→2→3→4→5→6所以展开后链表结构就是 1-2-3-4-5-6每个节点只有 right 指针left 全部为 null。难点在于“原地”两个字不能用额外的容器把节点先存下来再重新串起来所有的调整都得在树原有的节点引用上完成。很多初学者第一步想到的是先做一次先序遍历按顺序把节点塞进数组或队列然后遍历容器把指针重新串一遍。这样做当然能通过测试但面试官基本不会满意——因为额外空间是 O(n)而且完全没考到对树结构本身的理解。真正的考点在于如何在遍历的过程中就地调整指针既不丢失节点又保证顺序正确。1.2 为什么“先存再连”不是好方案我先说清楚这个问题的本质矛盾。二叉树每个节点有两个指针链表每个节点通常只有一个后继指针。把树展开成链表本质上是把一个二岔结构压缩成一条线性结构这必然涉及指针的重新指向。而树节点没有额外的“标记位”告诉你这个节点有没有被处理过所以你一边遍历一边改指针很容易把还没访问的子树给弄丢。举例来说先序遍历的顺序是根→左→右。如果当前在根节点 1你把它左指针置空把右指针指向左子树根 2这时节点 5 的访问路径就断了——因为 1 的右指针原本指向 5现在改成指向 2 了。如果你没有提前保存 5 的引用整棵右子树就丢了。这就引出一个关键点只要动了父节点的指针就必须先把被覆盖的引用保存下来。所以这道题表面考的是树的遍历实际上考的是链表指针操作的“安全性”。这也是为什么很多人在递归解法里容易写错的原因——不是不理解先序而是没处理好“保存现场”。1.3 先序遍历与展开顺序的对应关系展开顺序等于先序遍历这个信息至关重要。先序遍历是“根→左→右”那么展开后的链表里任意一个节点 cur它的 next 要么是 cur 的左子树先序序列的第一个节点也就是 cur-left如果存在要么是 cur 在祖先路径上第一个未访问的右子树根节点。这句话比较绕我举个例子。上面那棵树1 的下一个是 2因为 1 有左孩子所以 next 是左孩子 2。2 的下一个是 3因为是 2 的左孩子。3 的下一个是 4因为 3 没有左孩子它的 next 是父节点 2 的右孩子 4。4 的下一个是 5因为 4 是叶子它的 next 需要回溯到祖先节点 2 的父节点 1 的右孩子 5。看到没有展开链表里的“后继关系”并不像普通链表那么直观它跨越了树的层级需要回溯祖先信息。这就是为什么单纯靠当前节点判断 next 指向哪里很困难必须借助递归栈、显式栈或者一种非常巧妙的“前驱节点”思路。这个“前驱节点”的思路正是最优解的核心。2. 解法一递归先序思路最直接2.1 递归展开的核心原理既然展开顺序是先序最自然的想法就是用递归做先序遍历边遍历边改结构。但直接“边遍历边改”有一个致命问题递归到左子树的时候父节点的右指针已经被改掉了右子树信息丢失。所以常见的递归解法是分两步——先递归展开左子树再递归展开右子树最后把左子树展开后的链表接到根节点和右子树展开后的链表之间。具体来说对每个节点 root递归展开 root 的左子树得到一个已经展平的链表头节点是 root-left尾节点是左子树中最后一个被访问的节点。递归展开 root 的右子树得到另一个展平链表。把 root 的右指针指向左子树展平后的头节点左指针置空。找到左子树链表的尾节点把它的右指针指向右子树展平后的头节点。这里的关键是“找左子树链表的尾节点”。有的实现会单独写一个函数返回链尾有的实现会先遍历到尾部。缺点很明显如果树比较深找尾节点需要额外遍历时间复杂度会退化。更优雅的方式是让递归函数返回“展开后链表的尾节点”。2.2 返回尾节点的递归实现我直接给一个 C 实现递归函数返回展平后链表的尾节点这样父节点可以直接拿到左子树的尾部去拼接class Solution { public: void flatten(TreeNode* root) { flattenAndReturnTail(root); } // 返回展平后链表的尾节点如果 root 为空则返回 nullptr TreeNode* flattenAndReturnTail(TreeNode* root) { if (!root) return nullptr; if (!root-left !root-right) return root; TreeNode* leftTail flattenAndReturnTail(root-left); TreeNode* rightTail flattenAndReturnTail(root-right); // 如果左子树存在需要把左子树插到 root 和右子树之间 if (leftTail) { // 先把原来的右子树存起来 TreeNode* rightSubtree root-right; // 左子树移到右侧 root-right root-left; root-left nullptr; // 左子树的尾接到原来的右子树上 leftTail-right rightSubtree; } // 如果右子树为空链尾就是左子树的尾部否则是右子树的尾部 return rightTail ? rightTail : leftTail; } };这段代码有几个细节要提醒。第一递归展开右子树之前没有先保存 root-right不需要因为 right 子树展开后还是以 right 为头的链表递归函数里会返回它的尾节点而头节点仍然是 root-right。但是这里有个陷阱如果你先调用了 flattenAndReturnTail(root-left)它会把左子树内部结构调整好但此时 root-right 还没动所以可以先保存 rightTail。我代码里先用 leftTail 和 rightTail 接收返回值再去修改 root 的指针这个顺序是对的。第二为什么返回值是rightTail ? rightTail : leftTail因为如果右子树为空整个链表的尾部就是左子树展平后的尾部如果右子树不为空左子树被插入到中间尾部自然是最初右子树展平后的尾部。这个逻辑非常多初学者会写错写成总是返回 rightTail结果右子树为空时返回 nullptr父节点就丢了链尾信息。2.3 递归解法的时间与空间复杂度递归解法的时间复杂度是 O(n)因为每个节点被访问的次数是有限的递归函数对所有节点各调用一次加上找尾节点不需要额外遍历因为返回值直接给了整体是线性时间。空间复杂度是 O(h)h 是树的高度由递归调用栈决定。最坏情况下树退化成链表递归深度为 n空间 O(n)最好情况下完全平衡空间 O(log n)。这个空间复杂度是“还可以接受”的水平但面试官通常会追问一句“能不能不用递归也不占额外空间”这时候就要引出迭代和前驱节点的解法了。递归的优势是代码简洁、思路清晰劣势是栈深度受限、不是严格意义上的 O(1) 空间。3. 解法二迭代前序用显式栈不丢节点3.1 为什么需要一个栈递归用了系统调用栈来保存“右边还没访问的祖先节点”如果我们不想用递归就得自己维护一个栈来模拟这个过程。迭代前序遍历二叉树的套路大家应该很熟了从根开始访问当前节点右孩子入栈左孩子入栈先右后左保证左孩子先出栈。但这道题的问题是访问当前节点后要立刻修改它的指针结构。如果修改太早会不会破坏后续遍历举个例子。用栈做先序遍历访问 1 之后按顺序应该访问 2而栈里已经按“先右后左”压入了 5 和 2。如果我们把 1-right 改成 2把 1-left 置空栈里的 5 和 2 不受影响因为它们是通过栈保存的引用而不是通过 1 的右指针去找。所以用栈做迭代是安全的——只要你在修改结构之前已经把所有需要访问的节点压进栈了。3.2 迭代解法代码及执行过程class Solution { public: void flatten(TreeNode* root) { if (!root) return; stackTreeNode* stk; stk.push(root); while (!stk.empty()) { TreeNode* cur stk.top(); stk.pop(); // 先把右左孩子压栈注意先右后左 if (cur-right) stk.push(cur-right); if (cur-left) stk.push(cur-left); // 修改指针把左孩子放到右指针上左指针置空 if (!stk.empty()) { cur-right stk.top(); } else { cur-right nullptr; } cur-left nullptr; } } };这段代码的核心思路是栈顶元素就是当前节点 cur 的下一个应该访问的节点。因为先序遍历下cur 访问完之后下一个要访问的节点就是栈里栈顶那个。所以我们直接把 cur-right 指向栈顶即可。这个逻辑非常巧妙它把“找下一个节点”的任务完全交给了栈。执行一遍大家就明白了。初始栈[1]弹出 1压入 5 和 2栈变成[5,2]栈顶是 21-right 指向 2。弹出 2压入 4 和 3栈变成[5,4,3]2-right 指向 3。弹出 3无孩子栈[5,4]3-right 指向 4。弹出 4无孩子栈[5]4-right 指向 5。弹出 5压入 65-right 指向 6。弹出 6栈空6-right 置空。链表为 1-2-3-4-5-6完全正确。这里有个容易忽略的点栈顶元素可能是当前节点的右兄弟也可能是祖先的右子树。比如 3 的下一个节点是 4而 4 是 2 的右孩子3 和 4 本身并没有直接父子关系。栈帮我们保存了这层跨越关系这正是迭代解法能工作的根本原因。3.3 迭代解法的优缺点分析迭代解法空间复杂度是 O(n)因为栈里可能同时存在很多节点。最坏情况比如树是“之”字形结构栈里要保存一整条右子树链空间 O(n)。虽然比递归少了一些函数调用开销但空间上并没有质的提升。时间复杂度同样是 O(n)每个节点入栈出栈各一次。优点是第一代码比较短逻辑清晰第二不会因为递归太深导致系统栈溢出可以处理高度很大的树。在工程上如果你拿到的树可能深度达到十万级递归方案直接爆栈迭代方案就能扛住。但 LeetCode 这道题的测试数据一般不会那么极端所以递归也能过。面试的时候如果只写出这个解法面试官一般会认可你能做出来但距离“优秀”还差一步。因为他期待的可能是下面这种空间 O(1) 的神级解法。4. 解法三原地前驱节点法空间 O(1) 的教科书解4.1 前驱节点法的核心洞察前面说过展开顺序的先序遍历是“根→左→右”所以在某一个节点 cur如果 cur 有左子树那么 cur 的左子树里最后一个被访问的节点就是 cur 的左子树中最右下的那个节点。这个最右下的节点在先序序列里恰好排在左子树最后一个位置下一个才轮到右子树。换句话说cur 的左子树的最右下节点就是 cur 右子树的前驱节点——它的右指针应该指向 cur 的右子树。这个思路的名字叫“前驱节点法”也叫 Morris 遍历思想的简化版。它的核心操作是从根节点出发设当前节点为 cur。如果 cur 有左子树找到左子树的最右节点 prev。把 prev-right 指向 cur-right这一步把右子树接到了左子树链表的末尾。把 cur-right 指向 cur-left即把左子树移到右侧。把 cur-left 置空。然后 cur cur-right继续处理下一个节点如果 cur 没有左子树就直接 cur cur-right。这个算法最妙的地方在于它把右子树“挂”到了左子树最后一个节点的右边然后再把左子树整体搬到 cur 的右边。这样cur 的右指针指向的是展平后的下一段链表头而且整个过程中没有使用任何额外空间也不需要栈或递归。4.2 完整实现与分步图解class Solution { public: void flatten(TreeNode* root) { TreeNode* cur root; while (cur) { if (cur-left) { // 找到左子树的最右节点 TreeNode* prev cur-left; while (prev-right) { prev prev-right; } // 把右子树接到左子树链表的末尾 prev-right cur-right; // 把左子树移到右边 cur-right cur-left; cur-left nullptr; } // 继续处理下一个节点 cur cur-right; } } };这个代码只有十几行但确实不好理解。我拆开一步一步走。还是那棵树1 有左子树左子树根是 2。找 2 的最右节点2-right 是 44 没有右孩子所以 prev 是 4。把 4-right 指向 1 原来的右子树根 5。此时结构变成1 的左子树是 22 的右孩子是 44 的右孩子是 55 的右孩子是 6。然后 1-right 指向 21-left 置空。树变成1-2-3-4-5-6 这样的雏形了但是 3 还没接入别急2 还有左孩子 3。然后 cur 移动到 2。2 有左子树左子树根是 3。找 3 的最右节点就是 3 自己。把 3-right 指向 2 现有的右子树根 42-right 指向 32-left 置空。这时确实变成了 1-2-3-4-5-6。然后 cur 移动到 3。3 没有左子树cur 移动到 4。4 没有左子树cur 移动到 5。5 没有左子树cur 移动到 6。结束。注意一个细节找最右节点 prev 时代码用的是while (prev-right)但这时 prev-right 可能已经不是最初的 2 的右孩子了因为 2 的右子树在上一轮已经整体接到 4 后面了。不过没关系我们找的就是当前左子树的最右节点即使它已经挂上了原来右子树的节点最右节点依然是整个大链表的尾部把它接到 cur-right 正好是“把 cur 的右子树接到左子树链表末尾”逻辑依然成立。4.3 为什么这是最优解以及实现中的坑前驱节点法的时间复杂度是多少看起来外层循环是 O(n)内层找最右节点可能也要 O(n)整体会不会是 O(n²)这就需要仔细分析。实际上每个节点的 right 指针最多会被内层循环访问一次。因为一旦某个节点被确定为某一个左子树的最右节点它的 right 就会被赋值指向右子树。之后这个节点不可能再成为其他节点的“最右节点”被遍历到。所以总的时间复杂度是 O(n)。这一点很多文章都没说清楚我在这里重点强调。空间复杂度是严格 O(1)因为没有用栈、没有递归、没有额外容器。这在面试中是最亮眼的点。不过这个解法有三个容易踩的坑第一个坑是内层找最右节点的终止条件。如果写成while (prev-right)没问题但如果树里原本有环题目保证没有环但你写通用逻辑时要注意就危险了。这道题不需要判环。第二个坑是指针修改的顺序。必须先执行prev-right cur-right再执行cur-right cur-left。如果反过来先让 cur-right 指向左子树左子树最右节点的右指针要指向原来的右子树但原来右子树可以通过cur-right拿到吗拿不到了因为 cur-right 已经被覆盖成左子树了。所以必须先接右再移左。第三个坑是循环变量 cur 的移动。处理完当前节点后cur 应该移动到 cur-right。但你可能会想cur-right 在修改后指向了左子树那移动到的就是左子树根节点这正是下一个要处理的节点。如果 cur 没有左子树cur-right 指向的就是原来的右子树或已经接好的链也没有问题。不要画蛇添足地去判断 cur 是否有左孩子再决定怎么移动直接cur cur-right就行了。这个解法也常常被拿来和 Morris 中序遍历做对比两者的核心思想是一致的利用树中空闲的 right 指针来暂存后继信息。如果你理解了这个解法再看 Morris 遍历就会容易很多。5. 常见问题与排查技巧实录5.1 递归返回值总是搞错怎么办很多人在写递归返回“尾节点”的版本时返回值经常写错。这里教大家一个判断方法你只需要问自己一个问题——这个根节点所在的子树展平后最后一个被访问的节点是谁如果右子树存在那一定是右子树展平后的尾节点如果右子树为空但左子树存在就是左子树展平后的尾节点如果左右都为空就是根节点自己。把这个逻辑写成三元表达式就是return rightTail ? rightTail : (leftTail ? leftTail : root)注意叶子节点要先判断。还有一种更简单的做法很多人的递归不返回尾节点而是返回头节点然后在主函数里“找到尾部再接”。这种做法思路简单但是时间复杂度会退化到 O(n²)因为每个子树都要遍历找尾。如果是自己练习可以试试但面试时最好给出 O(n) 的递归版本。5.2 迭代法里指针修改导致遍历错乱用过迭代栈解法的人可能遇到一种诡异的情况链表结构看起来是对的但有些节点重复出现形成环。这通常是因为修改cur-right的时候没有考虑到当前节点原本的 right 子树是否还在栈里。回到迭代代码if (cur-right) stk.push(cur-right); if (cur-left) stk.push(cur-left);这一步必须在修改 cur-right 之前完成。如果你先改了 cur-right再想压栈右子树那压进去的已经是新指向的节点了原有的右子树直接丢失甚至可能出现环。所以顺序必须是先压栈再改指针。这个顺序问题我见过很多人踩坑包括一些工作两三年的开发。5.3 前驱节点法处理空左子树的特殊情况前驱节点法里如果当前节点 cur 没有左子树我们什么都不做直接cur cur-right。这里有个隐性前提cur 的右子树必须是“已经展平”或者“尚未处理但能通过右指针访问到”的状态。有人会问如果 cur 没有左子树但是 cur 的右子树里还有左孩子呢比如一棵树是 1-right22-left3。循环到 cur2 时发现 2 有左子树就会处理。所以不存在“漏处理”的问题。前提是你对每个节点都会走到而外层循环正是从根沿着 right 指针一路走到底所以每个节点都会成为 cur。5.4 一个万能的自测方法这道题做完了想自测不要光看 LeetCode 判题结果自己也可以写一个校验函数从根节点出发沿着 right 指针走一遍用 vector 收集节点值同时对原树做一次先序遍历收集值最后对比两个序列是否完全一致。顺手檢查每个节点的 left 是否为空。这个小工具无论是本地 IDE 还是在面试时现场写都能快速暴露问题。我平时刷题凡涉及链表重连的题目都会写这种校验器比 naked eye 靠谱得多。6. 扩展从这道题到二叉树与链表实战场景6.1 这道题在面试中的常见变体面试官一般不会只满足于让你笔写一遍后面往往会跟几个变体问题我整理了一下高频的展开成链表的顺序改成中序怎么办思路完全一致只是把“先序”改成“中序”前驱节点法依然适用只是找的是中序遍历下的前驱。展开成链表顺序改成后序怎么办后序需要先处理左右子树再处理根用递归反而更自然迭代和前驱节点法要复杂一些需要逆序思维。要求返回展开后的链表头节点而不是原地修改怎么办更简单先序遍历存 vector 再串。要求展开后是双向链表LeetCode 426 原题怎么办那就要同时维护 left 和 right 指针本质上就是中序遍历加指针连接。这种“变体”之所以重要是因为面试官想看你是否真正理解了遍历与指针之间的关系而不是背题。6.2 二叉树展开为链表的工程应用场景很多人刷完题会问这东西现实里到底有什么用在纯业务开发里确实很少直接用到但在底层系统里场景并不少。一个典型的场景是内存池或对象池的节点复用。有些系统需要把大量空闲对象用链表串起来管理当对象本身是树形结构的一部分时你可以在对象空闲时复用它的左指针或右指针来构建空闲链表。比如某些内存分配器、游戏引擎的 Entity 组件释放后的复用机制就会用到类似“把树结构临时改造成链表”的技巧。这种场景不需要严格的先序或中序但“利用已有指针构建线性结构”的思想是一致的。另一个场景是序列化与反序列化。把一棵二叉树存到磁盘或网络上通常要按某种遍历序输出。如果希望“只存 right 指针不存 left 指针”来节省空间可以先做一次展开再按链表顺序输出节点值。反序列化时再通过某种规则重建树。很多嵌入式环境、数据库索引的 dump 和 load 就有类似做法。热词里提到“嵌入式 二叉树之avl树”“嵌入式二叉树”其实就是这个道理——嵌入式设备内存紧张能少一个指针字段就少一份开销展开成链表后能极大简化存储结构。还有一个场景是编译器和解释器里的 AST 线性化处理。抽象语法树在做某些优化、指令调度、或者生成中间代码时需要把树形结构展平成线性指令流。虽然真正的编译器不会直接调用 LeetCode 114 的代码但“树形结构→线性序列”的思维模式是完全一致的。理解这道题的展开过程能帮助你理解为什么有些编译器优化要重建控制流图而不是直接在 AST 上做。6.3 和其他二叉树热门题目的连点成线这道题和“二叉树的中序遍历”“Morris 遍历”“二叉树的最近公共祖先”等题目是高度关联的。如果你把“前驱节点法”吃透了Morris 中序遍历的“右指针暂存后继”思想就很好理解了。热词里提到“搜索二叉树”“线索二叉树”其实线索二叉树本质上就是在树的空指针里存放前驱/后继信息和这道题里“把左子树最右节点的右指针指向右子树”的做法有异曲同工之妙。可以说LeetCode 114 是理解“线索化”概念的最小切口。另外“链表和树”这个热词也点明了这类题的考察本质树和链表之间并不是泾渭分明的树可以看作链表的“分叉版本”链表可以看作树的“退化形态”。理解了这一点很多涉及树到链表的题目就不需要背题而是从“如何用有限指针表达线性序”这个角度去推导。7. 总结与个人实操体会这道题刷完给我的最大感受是递归解法让你学会“用什么顺序处理问题”迭代解法让你学会“如何自己管理状态”前驱节点法让你学会“如何利用已有结构省空间”。三种解法恰好对应了算法能力的三个层次能用、会优化、能设计。如果你现在刷题正处在第一层不要急于去看最优解先把递归和迭代两种解法写得滚瓜烂熟再花时间理解前驱节点法。这不是浪费时间而是在帮你建立“同一道题有多种技术路径”的思维习惯。我个人的刷题习惯是第一遍只写递归写完不看题解第二天再独立写迭代第三遍再对着最优解的思路推演前驱节点法。这种间隔重复的效果比一天内刷三遍要好得多。原因很简单前两遍帮你建立了“递归和栈的对应关系”第三遍才能水到渠成地理解“为什么不用栈也能保存后继”。最后分享一个调试小技巧。这类树的题目建议你把测试用例画成图而不是只凭脑中想象。我在白板上推导前驱节点法时会用三种颜色的笔分别标出当前节点、左子树最右节点、右子树头节点。这样三个角色清晰了指针怎么改一画就明白。笔试时也可以用这个思路哪怕只是草稿纸上画出来写代码的准确率都会高很多。