整理算法题解这块，我一直有个习惯：每做完一道有代表性的题目，就会顺手把解法思路和踩坑过程记录下来。今天想聊的这道LeetCode 114 二叉树展开为链表，算是我印象里“看似简单、写起来却容易绕进去”的典型题目。它考察的点非常集中：树的遍历、节点指针的原地修改、以及空间复杂度的取舍。很多人第一次遇到它，脑子里立刻想到的解法可能是“先遍历一遍，把节点存下来，再重新串起来”——思路没错，但真动手写的时候，往往会因为一个细节没想清楚，导致结果完全不对。

这篇文章我会按照自己实际刷题时的思考路径来写：先讲清楚题目到底在问什么，为什么第一版解法容易踩坑，再给出三种从易到难的解法，最后聊聊调试这类二叉树链表问题时的一些实用技巧。如果你正在刷二叉树相关的题目，或者准备面试时遇到“原地修改树结构”这类要求，这篇文章应该能帮你省下不少折腾的时间。

1. 先看懂题目：它要的不是“新链表”，而是“原地改造”

114 的关键约束：给定一棵二叉树，要求把它“展开”成一个单链表。展开后的链表顺序必须和这棵树的先序遍历顺序一致。链表仍然放在原来的树节点里：每个节点的right指向链表的“下一个节点”，left统一置为null。

这里最容易忽略的点就是“仍然使用原来的树节点”。换句话说，你不能新建一堆链表节点，把val拷过去完事。题目希望你在原有的TreeNode对象上动手，把左子树拆掉、右指针重新连接。真正的面试场景里，面试官看到你用额外数组来存储节点指针，通常会追问一句：“能不能不开额外空间？”这时候如果你还没思考过原地展开的做法，就容易卡住。

还有一个小细节，很多人初读题目会误以为结果是“中序遍历顺序”。实际上题目明确规定是先序（根 -> 左 -> 右）。这个顺序直接决定了后续解法的压栈顺序和指针操作方式。我记得自己第一次手写迭代法时，就是因为把“先序”和“中序”的入栈顺序搞混，结果链表的顺序错得离谱。

再补充说明一下“展开成链表”之后树会变成什么样：从根节点出发，一路顺着right走，就能像遍历单链表一样访问到所有的节点。任何一个节点的left都是空的。如果你最后拿inorder或者层级遍历去验证，那就完全搞错验证逻辑了。正确验证方式只有一个：从根开始，不断取right，按顺序输出val，再和先序遍历结果逐项对比。

2. 最直觉的解：先序遍历收集节点，再重建链表

大多数人看到这道题的第一反应，应该是下面这个流程：

1. 先对二叉树做一次先序遍历，把遇到的节点指针依次放进一个数组。
2. 遍历这个数组，把left全部置空，把right指向数组里的下一个节点。

思路非常直白，代码也不难写。如果你只是在 IDE 里自己跑着玩，这个解法完全足够。这里给出一个 C++ 版本的示例：

class Solution { public: void flatten(TreeNode* root) { if (!root) return; vector<TreeNode*> 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, vector<TreeNode*>& 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还有两个指针；节点值只是这块空间里的一个字段。我们一旦把节点指针存入数组，就相当于记下了“这块空间在哪”，之后无论怎么修改指针结构，都不影响“通过数组下标找到这块空间”这个事实。

这也是为什么这种收集法在修改指针时可以放心大胆地操作。但反过来，如果你用递归函数存的是vector<int>，那你拿到的只是散落的数值，丢失了节点之间的天然联系，重建链表时还得重新分配空间。这道题既然明确要求用原节点，那收集指针就是唯一合理的方式。以后你写其他需要“重排树节点顺序”的题目，比如把二叉树展开成双向链表，也同样是这个道理：必须先存引用/指针，不能只存值。

2.2 这个方案的致命伤：空间复杂度不是 O(1)

数组存储最多需要 n 个指针，每个指针 8 字节（64 位系统），一棵上万节点的树，光数组就要占几十 KB 到几百 KB。这在算法竞赛或者面试的场景里不算特别夸张，但题目如果明确要求原地完成，这个方案就是一个不合格答案。

从数据结构的角度看，树的本质就是通过指针连接的一组节点。我们完全可以通过“拆左挂右、借用后继指针”的方式，在遍历的过程中直接完成链表化。这也是接下来两种解法的核心思路。

3. 迭代版进阶解法：边遍历边改链，用栈守住现场

既然不让我们用数组存储全部节点，那就得换一种思路：在遍历树的同时，把已经访问过的节点串成链表。这里需要用到栈来模拟递归遍历，因为树的遍历天然自带“回溯”行为——走到某个节点的左子树尽头之后，还要回到该节点去处理右子树。栈的作用，就是帮我们记住“待访问的右子树”。

先直接给出我认为最好写的迭代解法，再解释它为什么成立：

class Solution { public: void flatten(TreeNode* root) { if (!root) return; stack<TreeNode*> 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。

1. 如果cur->left为空：直接移动到cur->right，处理下一个。
2. 如果cur->left不为空：从左子树出发，一路向右走，找到左子树的最右节点pre。
3. 将pre->right指向cur->right。这一步是把右子树“接”到左子树的最右侧，相当于把左子树和右子树通过一条临时道路连起来。
4. 将cur->right指向cur->left，cur->left置空。现在的当前节点，右指针已经指向了原来的左子树根节点。
5. cur移动到新的cur->right，继续循环。

这个过程可能光看文字不好理解，我画一个简单例子来说明。假设树是这样：

1 / \ 2 5 / \ \ 3 4 6

第一步，cur = 1，左子树存在。左子树 2 的最右节点是 4。把4->right指向1->right，也就是节点 5。然后把1->right指向2，1->left置空。此时树变成：

1 \ 2 / \ 3 4 \ 5 \ 6

注意这时候从 1 出发的右链是1 -> 2，而 4 的右指针指向了 5，4 变成了 5 的前驱。接着继续处理cur = 2。节点 2 的左子树是 3，左子树的最右节点就是 3 自己。把3->right指向2->right（此时是 4），然后把2->right指向3，2->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. 三种解法横向对比：什么时候用哪个

我习惯在刷题笔记里做一张横向表格，这样复习的时候一眼就能看到每种方案的差异。这里也分享出来：

从“可维护性”角度讲，我个人最喜欢第二种。它不是严格意义上的“原地”，因为用到了一个栈，但空间复杂度在普通二叉树场景下很小，而且逻辑非常符合直觉：先序遍历本来就用栈，边遍历边改链。第三种适合作为进阶补充，展示你对树结构指针操作的掌握深度。

另外值得强调的是，这三种解法的前序遍历顺序是完全一致的，所以最终展开的链表结果也是完全一致的。区别只是“什么时候改指针”以及“改指针时如何保留下一步要访问的节点”。理解了这一点，哪怕你将来遇到“展开成中序链表”“展开成后序链表”，也能用同一个思路推出来。

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 和 right，left 不置空就会被判错。

建议在代码里养成一个习惯：无论哪种解法，在把当前节点串到链表末尾时，统一执行一次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 延伸开去：一类题目的通用方法论

刷完这道题后，我总结了一个通用思路，适用于所有“按某种遍历顺序重排树节点”的题目：

1. 明确要求的遍历顺序。先序、中序、后序、层序？顺序不同，指针操作差别很大。
2. 考虑能否利用空指针做线索。尤其是要求 O(1) 空间时，树中总会存在足够的空指针，可以临时存储“后继位置”。
3. 修改指针前先画图。纸上推演一遍，确定哪些节点会丢失、哪些节点会形成环。
4. 注意遍历和修改的先后关系。如果一边遍历一边修改，就必须保证后续遍历仍能访问到未处理的节点。

顺着这个思路，你可以尝试自己解一下这几道题：

• “将二叉树展开为中序链表”（练习中序遍历和指针操作的组合）。
• “二叉树原地变成双向链表”（也就是 LeetCode 426 的风格，当然也可以用中序遍历）。
• “Morris 中序遍历”，里面同样有找前驱的动作，和 114 的第三种解法非常接近。

我自己的体会是，找左子树最右节点这个操作，在很多树相关的进阶题里都会遇到。把它练熟了，收益远超这单一题本身。

最后再分享一个写这类代码的习惯：我一般会把“找最右节点”抽成一个独立的小函数，比如findRightmost(TreeNode* node)，虽然 114 本身只有十几行代码，但抽出来之后逻辑会更清晰，测试的时候也更容易定位问题。如果将来遇到更复杂的变形，比如同时找最左节点、或者找后继节点，这些小工具函数都能直接复用。

如果你刷这道题时遇到什么不一样的坑，欢迎在评论区一起聊聊。刷算法题很多时候就是这样，看似简单的一道题，深挖下去能牵出一大片知识点。