整理算法题解这块我一直有个习惯每做完一道有代表性的题目就会顺手把解法思路和踩坑过程记录下来。今天想聊的这道LeetCode 114 二叉树展开为链表算是我印象里“看似简单、写起来却容易绕进去”的典型题目。它考察的点非常集中树的遍历、节点指针的原地修改、以及空间复杂度的取舍。很多人第一次遇到它脑子里立刻想到的解法可能是“先遍历一遍把节点存下来再重新串起来”——思路没错但真动手写的时候往往会因为一个细节没想清楚导致结果完全不对。这篇文章我会按照自己实际刷题时的思考路径来写先讲清楚题目到底在问什么为什么第一版解法容易踩坑再给出三种从易到难的解法最后聊聊调试这类二叉树链表问题时的一些实用技巧。如果你正在刷二叉树相关的题目或者准备面试时遇到“原地修改树结构”这类要求这篇文章应该能帮你省下不少折腾的时间。1. 先看懂题目它要的不是“新链表”而是“原地改造”114 的关键约束给定一棵二叉树要求把它“展开”成一个单链表。展开后的链表顺序必须和这棵树的先序遍历顺序一致。链表仍然放在原来的树节点里每个节点的right指向链表的“下一个节点”left统一置为null。这里最容易忽略的点就是“仍然使用原来的树节点”。换句话说你不能新建一堆链表节点把val拷过去完事。题目希望你在原有的TreeNode对象上动手把左子树拆掉、右指针重新连接。真正的面试场景里面试官看到你用额外数组来存储节点指针通常会追问一句“能不能不开额外空间”这时候如果你还没思考过原地展开的做法就容易卡住。还有一个小细节很多人初读题目会误以为结果是“中序遍历顺序”。实际上题目明确规定是先序根 - 左 - 右。这个顺序直接决定了后续解法的压栈顺序和指针操作方式。我记得自己第一次手写迭代法时就是因为把“先序”和“中序”的入栈顺序搞混结果链表的顺序错得离谱。再补充说明一下“展开成链表”之后树会变成什么样从根节点出发一路顺着right走就能像遍历单链表一样访问到所有的节点。任何一个节点的left都是空的。如果你最后拿inorder或者层级遍历去验证那就完全搞错验证逻辑了。正确验证方式只有一个从根开始不断取right按顺序输出val再和先序遍历结果逐项对比。2. 最直觉的解先序遍历收集节点再重建链表大多数人看到这道题的第一反应应该是下面这个流程先对二叉树做一次先序遍历把遇到的节点指针依次放进一个数组。遍历这个数组把left全部置空把right指向数组里的下一个节点。思路非常直白代码也不难写。如果你只是在 IDE 里自己跑着玩这个解法完全足够。这里给出一个 C 版本的示例class Solution { public: void flatten(TreeNode* root) { if (!root) return; vectorTreeNode* nodes; preorder(root, nodes); for (int i 0; i nodes.size(); i) { nodes[i]-left nullptr; nodes[i]-right (i 1 nodes.size()) ? nodes[i 1] : nullptr; } } void preorder(TreeNode* root, vectorTreeNode* nodes) { if (!root) return; nodes.push_back(root); preorder(root-left, nodes); preorder(root-right, nodes); } };时间复杂度和空间复杂度都是 O(n)。对于本地练习或者思路热身这个方案没有任何问题。但请注意一个关键细节数组里存的是节点指针不是节点值的拷贝。这意味着第二步“重建链表”修改的是原来的节点对象本身。如果你在第一步存的是int val这种值类型后续再想构造新链表就完全违背了题目“使用原节点”的要求而且需要重新new出一批节点空间和时间都会更差。另外有个很容易踩的坑递归收集节点后在重建阶段修改left/right并不会影响已经保存在数组里的指针。因为指针本身是节点的地址你修改的是地址指向的内容。第一次写的时候我还在担心“改掉right会不会导致数组里的节点丢失信息”实际上完全不会。真正要担心的是如果一边收集一边修改结构比如先修改root-left nullptr再也没法通过原来的root-left去递归遍历左子树那就会漏掉一大片节点。所以“先收集完再统一修改”这个顺序是这种解法能成立的关键。不过这种方法在面试时通常只能作为“思路正确但不够优化”的过渡方案。因为题目后面往往还有一句“你能否使用 O(1) 的额外空间完成”。就算没有这句话面试官也会很自然地追问一句“能不能省掉这个数组”。到这一步我们就得进入第二种解法了。2.1 为什么“存节点指针”而不是“存节点值”我在前面提到了一个实现细节这里想专门展开说几句。很多初学链表、树这类数据结构的读者容易把节点对象和节点值混为一谈。节点对象在内存里占据一块固定空间里面除了val还有两个指针节点值只是这块空间里的一个字段。我们一旦把节点指针存入数组就相当于记下了“这块空间在哪”之后无论怎么修改指针结构都不影响“通过数组下标找到这块空间”这个事实。这也是为什么这种收集法在修改指针时可以放心大胆地操作。但反过来如果你用递归函数存的是vectorint那你拿到的只是散落的数值丢失了节点之间的天然联系重建链表时还得重新分配空间。这道题既然明确要求用原节点那收集指针就是唯一合理的方式。以后你写其他需要“重排树节点顺序”的题目比如把二叉树展开成双向链表也同样是这个道理必须先存引用/指针不能只存值。2.2 这个方案的致命伤空间复杂度不是 O(1)数组存储最多需要 n 个指针每个指针 8 字节64 位系统一棵上万节点的树光数组就要占几十 KB 到几百 KB。这在算法竞赛或者面试的场景里不算特别夸张但题目如果明确要求原地完成这个方案就是一个不合格答案。从数据结构的角度看树的本质就是通过指针连接的一组节点。我们完全可以通过“拆左挂右、借用后继指针”的方式在遍历的过程中直接完成链表化。这也是接下来两种解法的核心思路。3. 迭代版进阶解法边遍历边改链用栈守住现场既然不让我们用数组存储全部节点那就得换一种思路在遍历树的同时把已经访问过的节点串成链表。这里需要用到栈来模拟递归遍历因为树的遍历天然自带“回溯”行为——走到某个节点的左子树尽头之后还要回到该节点去处理右子树。栈的作用就是帮我们记住“待访问的右子树”。先直接给出我认为最好写的迭代解法再解释它为什么成立class Solution { public: void flatten(TreeNode* root) { if (!root) return; stackTreeNode* stk; stk.push(root); TreeNode* prev nullptr; while (!stk.empty()) { TreeNode* cur stk.top(); stk.pop(); if (prev ! nullptr) { prev-left nullptr; prev-right cur; } // 注意要先压右子树再压左子树 // 因为栈是后进先出我们希望下一个弹出的是左子树 if (cur-right ! nullptr) { stk.push(cur-right); } if (cur-left ! nullptr) { stk.push(cur-left); } // 把左右子树指针切断避免后续操作干扰 cur-left nullptr; prev cur; } } };这段代码的核心逻辑可以这样理解栈里保存的是“未来要访问的节点”。每次弹出一个cur它就是本次要串到链表末尾的节点。prev表示链表中上一个节点我们需要把prev-right指向cur同时确保prev-left为空。这里一个非常容易写错的地方是在压栈之前不能先把cur-left和cur-right都置空。因为一旦你先把cur-right置空后面if (cur-right ! nullptr)就永远不成立了右子树就丢掉了。正确顺序是先把左右子树指针都取出来、完成压栈然后再放心地把cur-left置空。至于cur-right它马上会被下一个prev覆盖掉所以实际上不用在当前回合显式置空但为了代码语义清晰也可以在最终统一处理或者干脆在prev那一侧完成。3.1 理解“先压右、再压左”这步操作栈是后进先出。树先序遍历的顺序是根、左、右。那么当我们弹出一个节点时希望它的左子树节点优先被访问。因为栈顶元素会最先弹出所以我们应该让左子树处于栈顶附近即最后压入左子树。于是操作顺序就是“先压右再压左”。很多没完全理解栈的人总喜欢“先压左、再压右”写出来完全没问题可得到的却是“根、右、左”的顺序链表自然就反了。这个顺序我在其他题目里也经常用到比如用迭代法写先序遍历stk.push(root); while (!stk.empty()) { cur stk.top(); stk.pop(); visit(cur); if (cur-right) stk.push(cur-right); if (cur-left) stk.push(cur-left); }只要你理解了栈的 LIFO 特性就不会犯这个顺序错误。3.2 为什么这个解法可以做到“不需要存储所有节点”因为栈的深度最多等于树的高度而不是节点总数。极端情况下如果树退化成一个只有右子树的链那么栈里面始终只有一个节点空间复杂度为 O(1)如果是一棵满二叉树高度是 log n栈空间也只是 O(log n)。当然最坏情况比如一棵倾斜的树下栈可能存储 O(n) 个节点但对于普通二叉树来说它比第一种数组方案省得多。时间复杂度依然是 O(n)每个节点被压入一次、弹出一次、修改指针一次。没有任何多余的重复遍历。3.3 这个解法在面试里的定位我个人的建议是如果你在面试中遇到这题第一版直接写这个迭代解法是比较稳妥的。它不依赖递归不容易爆栈空间也足够优秀而且代码逻辑比较好向面试官解释。你可以先用一两句话说明思路“用栈做先序遍历同时维护一个前驱指针边访问边把当前节点接到前驱的右指针上。”然后把这道题作为“最优的实用解法”提出来。如果面试官继续追问“能不能用 O(1) 额外空间完成”这时候再抛第三种解法。如果你直接把第三种解法真正的 Morris 式原地展开写在第一版对面试官来说依然没问题但对你自己来说风险在于对机制理解不够深容易写错。所以我建议循序渐进。4. 真正的原地展开不借助栈把左子树变成右子树这是 LeetCode 114 最有技术含量的一种解法。它的核心思路可以总结成一句话对于当前节点 root如果它有左子树就找到左子树中最右边的节点也就是先序遍历中 root 的下一个节点的前驱位置把这个最右节点的 right 指向 root 的右子树然后把 root 的整个左子树搬到右边左指针置空。然后继续处理下一个节点。很多资料把这个解法称作“Morris 遍历”的变体。实际上它和 Morris 中序遍历确实有关系——都是利用树中空闲的right指针把某些节点临时连到后继上从而不需要额外空间。但在 114 这道题里我们做的是永久的结构修改不是临时的线索所以要仔细处理“搬家”的时机。来看具体的步骤拆解假设当前节点是cur。如果cur-left为空直接移动到cur-right处理下一个。如果cur-left不为空从左子树出发一路向右走找到左子树的最右节点pre。将pre-right指向cur-right。这一步是把右子树“接”到左子树的最右侧相当于把左子树和右子树通过一条临时道路连起来。将cur-right指向cur-leftcur-left置空。现在的当前节点右指针已经指向了原来的左子树根节点。cur移动到新的cur-right继续循环。这个过程可能光看文字不好理解我画一个简单例子来说明。假设树是这样1 / \ 2 5 / \ \ 3 4 6第一步cur 1左子树存在。左子树 2 的最右节点是 4。把4-right指向1-right也就是节点 5。然后把1-right指向21-left置空。此时树变成1 \ 2 / \ 3 4 \ 5 \ 6注意这时候从 1 出发的右链是1 - 2而 4 的右指针指向了 54 变成了 5 的前驱。接着继续处理cur 2。节点 2 的左子树是 3左子树的最右节点就是 3 自己。把3-right指向2-right此时是 4然后把2-right指向32-left置空。树变成1 \ 2 \ 3 \ 4 \ 5 \ 6继续处理cur 3它的左子树为空直接右移cur 4也同理直到cur变为空结束。最终从根到叶子形成一条完整右链。4.1 为什么这一步操作是安全的我们需要确认两件事第一把pre-right指向cur-right会不会丢失原有节点不会。因为pre原本的right一定是空它是左子树的最右节点左子树的任何节点都没有比它更右的节点。既然它本来就空着利用它来临时存放右子树的入口完全无副作用。第二把cur-right改为cur-left之后原先的右子树会不会丢不会。因为右子树的根已经被pre-right记录了等我们一路向右走到pre时自然能通过pre-right走到原来的右子树。这里有个常见的误区有人以为“先移动左子树到右指针”会导致后续遍历丢失左子树内部的节点。其实不会。我们在移动前并没有改变左子树内部的结构。cur-right cur-left只是把整棵左子树的根挂到了右边左子树内部的所有节点依然通过原来的左右指针连通着。后续处理过程中我们会逐步把每个节点的左子树也搬出来最终所有节点都会变成一条右链。4.2 代码实现class Solution { public: void flatten(TreeNode* root) { TreeNode* cur root; while (cur ! nullptr) { if (cur-left ! nullptr) { // 找到左子树的最右节点 TreeNode* pre cur-left; while (pre-right ! nullptr) { pre pre-right; } // 把右子树接到左子树的最右节点后面 pre-right cur-right; // 把左子树搬到右边 cur-right cur-left; cur-left nullptr; } // 继续处理下一个节点 cur cur-right; } } };这段代码非常短但是背后的思路值得好好品味。整个过程中我们只用了一两个辅助指针没有栈、没有递归额外空间就是 O(1)。时间复杂度呢表面上看每个cur都可能向左子树深处找最右节点似乎可能会重复扫描某些节点。但实际上每个节点最多被“找最右节点”这个过程碰到有限的次数——准确地说是被它的祖先作为左子树最右节点时访问一次——所以总时间复杂度仍然是 O(n)。这一点我一开始没想明白总觉得如果每个节点都找一个最右节点复杂度得像 O(n^2)。后来想通了每一次“找最右节点”走的路径都是某个节点的右链而右链上的节点被访问完并入链表后就不再需要被其他节点寻找了。所以整体是摊还 O(n)。4.3 关键风险点什么时候会无限循环有段时间我在 LeetCode 讨论区看到有人问“为什么我的原地算法超时了”。大多数情况是同一个原因在把左子树搬到右边之前没有切断cur-left。比如代码里漏掉cur-left nullptr这行后续虽然我们只沿着cur cur-right前进但某个节点的左子树依然挂着导致再次循环时又去“找左子树的最右节点”而且这个最右节点已经指向了右子树的一部分形成一个环形链表程序就永远走不完。另外还有一个隐患如果找最右节点的过程中没有判断pre-right是否为空而是用while (pre ! nullptr)一路向右走到头那当pre-right已经被临时接到右子树之后再次访问时就会循环。所以写while (pre-right ! nullptr)是绝对必要的。也就是说找前驱的时候停在一个节点的 right 为空的位置而不是走到空节点本身。这类“修改树结构的同时遍历”的题目特别容易因为指针指向关系没理清造成环或者丢节点。我的经验是每次动指针前先在纸上画出改动前和改动后的指针指向确认没有节点从“可达”变成“不可达”也没有形成环再落到代码上。5. 三种解法横向对比什么时候用哪个我习惯在刷题笔记里做一张横向表格这样复习的时候一眼就能看到每种方案的差异。这里也分享出来解法时间空间是否原地代码量推荐场景先序遍历收集数组O(n)O(n)否少易写仅用于热身或验证思路栈模拟先序遍历 前驱指针O(n)O(h)最坏 O(n)否中等面试稳妥答案原地找左子树最右节点O(n)O(1)是少但理解成本高追求最优解或面试加分从“可维护性”角度讲我个人最喜欢第二种。它不是严格意义上的“原地”因为用到了一个栈但空间复杂度在普通二叉树场景下很小而且逻辑非常符合直觉先序遍历本来就用栈边遍历边改链。第三种适合作为进阶补充展示你对树结构指针操作的掌握深度。另外值得强调的是这三种解法的前序遍历顺序是完全一致的所以最终展开的链表结果也是完全一致的。区别只是“什么时候改指针”以及“改指针时如何保留下一步要访问的节点”。理解了这一点哪怕你将来遇到“展开成中序链表”“展开成后序链表”也能用同一个思路推出来。5.1 从复杂度推演体会算法设计思路我们把这个题目的复杂度推演拆开来看。第一种解法遍历需要 O(n)存数组需要 O(n)重建需要 O(n)所以总时间 O(n)、总空间 O(n)。第二种解法每个节点进出栈一次指针操作都是常数级所以时间 O(n)空间取决于栈的最大深度对于高度为 h 的树是 O(h)。第三种解法每个节点被“找最右节点”的循环访问到有限次数摊还下来是 O(n)空间只用了固定几个指针O(1)。如果你平时准备算法题建议不只是背答案而是养成“复杂度推演”的习惯。比如这题里为什么第三种解法的时间复杂度不是 O(n^2)你如果能把这个道理讲清楚面试官对你的印象绝对不一样。6. 实战中的连环坑从报错到调试的完整排查链路最后来聊聊实际刷题时容易遇到的几个问题尤其是和热搜词里“写二叉树程序时为什么总是报运行时错误”相关的情况。6.1 空指针崩溃最常见的运行时错误就是访问了空指针。在这道题里最容易出空指针的位置是迭代法的压栈逻辑。假如你在root为空的时候不直接返回而是在while循环里取stk.top()那栈是空的对空栈调用top()就会直接崩溃。所以每个解法第一步都应该是if (!root) return;这个边界条件。再看另一种情况原地算法中找pre时如果cur-left为空但你依然尝试进入一个while (pre-right ! nullptr)循环那么pre本身是空指针程序也会崩溃。所以必须先判断cur-left ! nullptr再去找pre。6.2 展开后出现环这个比较隐蔽。我用1,2,5,3,4,#,6这棵测试树跑的时候发现有个版本认为“把左子树最右节点的 right 指向 root-right 之后整个链表会重复出现某些节点”。排查后发现问题出现在“没有提前保存cur-right”的情况下执行完pre-right cur-right后又紧接着做cur-right cur-left。如果cur的左子树最右节点恰好有某种联系操作顺序错了就会形成环。正确的操作顺序必须严格是找前驱 - 接右子树 - 搬左子树 - 清空左指针。一定不能先搬左子树再接右子树否则cur-right已经变成左子树再接过去的右子树就会丢失。这里分享一个调试小技巧执行完flatten之后用一个计数器顺着 right 指针遍历链表如果遍历次数超过节点总数那说明出现了环。正常情况遍历 n 次就应该结束最后一个节点的 right 为 null。在 LeetCode 上这种错误通常表现为 “Time Limit Exceeded”因为环导致遍历永远走不完。6.3 忘记切断左指针导致链表“分叉”有时候展开后的结果看起来是对的沿着right能走完所有节点。但如果你把每个节点的left都打印出来发现它们还挂着原来的子树那严格来说是不符合题目要求的。题目要求所有节点的 left 都为 null。更重要的是某些用例的验证逻辑可能同时检查 left 和 rightleft 不置空就会被判错。建议在代码里养成一个习惯无论哪种解法在把当前节点串到链表末尾时统一执行一次cur-left nullptr。第二种迭代法里因为压栈需要用到left所以压栈后立刻置空第三种原地法里是把左子树搬到右边后再置空。这个细节虽小但能避免很多莫名其妙的错误。6.4 如何构造自己的测试用例我通常会在本地准备几组不同类型的二叉树空树[]展开后应该还是空。只有一个节点[1]展开后不变。只有左子树[1,2,3]展开后应该是1 - 2 - 3。只有右子树[1,null,2,null,3]展开后应该是1 - 2 - 3。标准混合树[1,2,5,3,4,null,6]对应前面分析的那个例子。链表形态的树[1,null,2,null,3]此时原地算法应该直接跳过左子树判断一路右移既不能死循环也不能改错顺序。把这六组用例跑通正确性基本就有保障了。6.5 和“线索二叉树”的关系如果你接触过线索二叉树会发现第三种解法里“找左子树最右节点”的过程和线索化过程非常像。线索二叉树就是利用空余指针把节点的前驱和后继串联起来方便 O(1) 找到下一个节点。114 的原地展开本质上可以理解为我们不断利用左子树最右节点的空right指针把右子树“预埋”到正确位置然后一次性把左子树搬过去相当于一边线索化一边重建结构。理解这一层关系之后再遇到 Morris 遍历相关的题目上手会快很多。7. 从 114 延伸开去一类题目的通用方法论刷完这道题后我总结了一个通用思路适用于所有“按某种遍历顺序重排树节点”的题目明确要求的遍历顺序。先序、中序、后序、层序顺序不同指针操作差别很大。考虑能否利用空指针做线索。尤其是要求 O(1) 空间时树中总会存在足够的空指针可以临时存储“后继位置”。修改指针前先画图。纸上推演一遍确定哪些节点会丢失、哪些节点会形成环。注意遍历和修改的先后关系。如果一边遍历一边修改就必须保证后续遍历仍能访问到未处理的节点。顺着这个思路你可以尝试自己解一下这几道题“将二叉树展开为中序链表”练习中序遍历和指针操作的组合。“二叉树原地变成双向链表”也就是 LeetCode 426 的风格当然也可以用中序遍历。“Morris 中序遍历”里面同样有找前驱的动作和 114 的第三种解法非常接近。我自己的体会是找左子树最右节点这个操作在很多树相关的进阶题里都会遇到。把它练熟了收益远超这单一题本身。最后再分享一个写这类代码的习惯我一般会把“找最右节点”抽成一个独立的小函数比如findRightmost(TreeNode* node)虽然 114 本身只有十几行代码但抽出来之后逻辑会更清晰测试的时候也更容易定位问题。如果将来遇到更复杂的变形比如同时找最左节点、或者找后继节点这些小工具函数都能直接复用。如果你刷这道题时遇到什么不一样的坑欢迎在评论区一起聊聊。刷算法题很多时候就是这样看似简单的一道题深挖下去能牵出一大片知识点。