刷算法题的时候最怕遇到那种“明明思路清楚一写就崩”的题LeetCode 114“二叉树展开为链表”就是典型代表。题目本身要求把一棵二叉树按照前序遍历顺序原地展开成一条单链表所有左指针置空右指针直接指向下一个节点。这道题是算法题解记录里绕不开的一题它把二叉树遍历、链表操作、递归与迭代、空间复杂度优化全串在了一起既能考基本功又能考代码稳定性。很多人卡住不是因为不懂前序遍历而是因为对指针/引用的修改顺序不够敏感改着改着就把树的结构弄丢了。这篇文章我会把自己刷这道题时的完整思考过程、几种解法优劣、以及踩过的运行时错误全部写出来。不管你是刚开始学数据结构与算法还是在准备面试都能从中拿到可以直接复用的思路和代码。1. 先把题目和考点看透1.1 题目到底在讲什么题目给定一棵二叉树要求把它展开为链表。展开后的链表顺序和这棵树的前序遍历顺序完全一致。什么意思举个例子一棵最简单的二叉树根节点是1左孩子是2右孩子是52的左孩子是3右孩子是45的右孩子是6。前序遍历结果就是[1, 2, 3, 4, 5, 6]。展开之后这棵树要变成一条单链每个节点的left指针必须为nullright指针指向下一个节点最后一个节点的right也为null。这里的“原地”两个字很关键。它要求你不额外创建一棵新树也不允许用一个O(n)的容器把所有节点存下来再重建。当然不同解法对“原地”的理解不太一样但主流的面试要求是要么用递归的隐式栈要么干脆做到O(1)额外空间。我刚接触这道题时第一时间想到的是用一个vector存前序遍历结果然后把每个节点的left置空、right指向列表里的下一个节点。这个方法逻辑最简单但空间复杂度也是O(n)面试官往往会追问一句能不能不借外部存储所以这道题真正要考察的不是你会不会前序遍历而是你能不能在不破坏原树的情况下通过调整指针把树当场改造成链表。这里面的核心矛盾在于前序遍历要先访问根再访问左子树最后访问右子树。但如果你先把root的right指向了左子树的根那么原本的右子树就丢了。不把这一点想清楚代码就很容易报运行时错误。1.2 考点藏在哪些细节里这道题表面是二叉树题骨子里却是链表操作题。它考察的能力至少有三个维度。第一是二叉树遍历的熟练度。展开顺序就是前序遍历顺序所以你必须对“根左右”的访问顺序有肌肉记忆。第二是链表指针重连能力。单链表插入、拼接、找尾节点这些基本功在这道题里会被放大成“指针丢失”的高危操作。第三是空间复杂度的敏感度。递归解法虽然简洁但递归栈深度等于树高迭代Morris解法能把额外空间压到O(1)这背后是对中序前驱/线索化思想的理解。我建议刷题时不要只满足于跑通一种写法。你至少要会两种一种递归好懂一种迭代空间省。这样面试时既能快速讲思路又能展示你了解“为什么递归不是最优”。下面我就按从易到难的顺序把三类解法逐个拆开讲。2. 三种常见解法从易到难2.1 最直观先序遍历存数组再重建这个思路一句话就能说清先前序遍历整棵树把节点指针按顺序存进一个vector然后遍历这个vector依次把每个节点的left设为null、right设为下一个节点。我最早就是用这个思路做出来的代码非常简单void flatten(TreeNode* root) { 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)对于刷题来说已经很稳。但为什么面试里不推荐只用这个因为“原地”的约束没有完全体现。vector额外占用了n个指针的内存严格来说不算真正的原地。而且这道题考察的恰恰是在遍历过程中原地改写结构的能力如果依赖存储就失去了练习价值。不过作为基线解法它很有意义拿它对照其他解法你能明显看出哪种写法更考验细节。2.2 递归展开简洁但特别容易掉坑递归解法在思路上比存数组更进一层对每个节点先递归展开左子树再递归展开右子树然后把展开后的左子树接到root的right位置把展开后的右子树接到左子树的末尾。这样整体顺序依然是根、左、右。我第一次写这个版本时犯了一个经典错误没有先保存原右子树直接执行root-right root-left结果右子树整个找不到了。正确写法必须先暂存右子树void flatten(TreeNode* root) { if (!root) return; flatten(root-left); flatten(root-right); TreeNode* oldRight root-right; root-right root-left; root-left nullptr; TreeNode* tail root; while (tail-right) tail tail-right; tail-right oldRight; }分析一下这段代码的执行过程。假设当前节点有左子树和右子树递归结束后左子树内部已经是一条链右子树内部也已经是一条链。然后把root的right指向左链的头再把左链的尾节点指向原来的右链头。最后把root的left清空。这个版本的时间复杂度不是严格O(n)因为在每个节点上都要用while循环找左链尾节点。如果树是歪的比如每个节点都没有右子树但都有左子树那么每一层都要下探到底总体会退化成O(n^2)。面试官对这个敏感的话可以继续优化。优化方法是让递归函数返回“展开后链表的尾节点”这样就不用重复扫描。代码如下TreeNode* flattenHelper(TreeNode* root) { if (!root) return nullptr; TreeNode* leftTail flattenHelper(root-left); TreeNode* rightTail flattenHelper(root-right); if (leftTail) { leftTail-right root-right; root-right root-left; root-left nullptr; } return rightTail ? rightTail : (leftTail ? leftTail : root); } void flatten(TreeNode* root) { flattenHelper(root); }这个写法需要特别注意返回值的逻辑。右子树有尾节点就优先返回右尾否则返回左尾再否则返回root自己。这样上层拿到尾节点后可以直接把上层左链的尾接到上层右链头上不用再遍历一遍。用递归处理树结构时有一个通用原则不要只顾着修改当前节点要确保递归函数向上层返回的信息足够完成拼接。2.3 迭代O(1)把左子树嫁接给右子树递归虽好但有些面试官会继续要求“能不能不用递归额外空间做到O(1)”。这就需要迭代版的核心套路每遇到一个有左孩子的节点就找到它左子树中的最右节点前驱节点然后把当前节点的右子树接到这个前驱节点的右边再把左子树整体移到右子树位置最后把当前节点的left置空。代码看起来很短但逻辑非常密集void flatten(TreeNode* root) { TreeNode* cur root; while (cur) { if (cur-left) { TreeNode* predecessor cur-left; while (predecessor-right) { predecessor predecessor-right; } predecessor-right cur-right; cur-right cur-left; cur-left nullptr; } cur cur-right; } }这段代码没有使用栈也没有使用递归每次只是调整当前节点左右的指向。为什么这样能保证前序顺序因为当前节点处理完之后右指针指向的是原先左子树的根节点下一个while迭代就会进入左子树处理左子树内部的节点。等左子树全部处理完通过之前挂在前驱节点末尾的右子树指针自然就回到了原右子树。这个方法理解起来有点像“滚雪球”每处理一个节点就把它的左子树整体搬到它和原右子树之间同时保证原右子树不会丢。最终所有节点都像多米诺骨牌一样按前序串成一条线。3. 亲手跑一遍三个关键步骤拆解3.1 左子树最右节点为什么是关键先生在上面这个迭代解法里最核心的操作是找左子树最右节点。你要想清楚一个问题当cur有左孩子时cur的前驱节点是谁所谓前驱就是前序遍历中在cur之前最后一个被访问的节点。在cur的左子树中最右下的节点就是它。把这个前驱接到cur的右子树头上就能让前驱的right指向原右子树的首个节点从而保证遍历完左子树后能跳回右子树。我手动走一遍样例会更清楚。假设树是1 / \ 2 5 / \ \ 3 4 6cur 1时左孩子是2找到2所在的左子树最右节点4。因为4-right本来是null把它指向cur-right也就是5于是原本的4变成了一条线4-5-6。接着cur-right cur-left即1-21-left置null。这个时候从1开始沿着right走顺序是1-2-3-4-5-6吗结果是1-22-33-44-55-6完全正确。接着cur 2左孩子是3左子树最右节点就是3。把3-right指向cur-right也就是4此时4已经在前面接上了5-6这个过程不会丢东西。再把2-right指向32-left置null。链表顺序依然正确。这一步的关键不是代码而是理解“前驱节点是左右子树之间的桥”。当你把左子树整体搬到右边之前必须先把右子树挂在某个不会断的位置。这个位置就是左子树最右节点因为前序遍历中它正好是左子树里最后被访问的节点。3.2 空指针和悬挂指针的防范写二叉树程序时为什么总是报运行时错误八成是因为空指针解引用和丢失指针。这道题里两个隐蔽点你一定要盯死。第一个是cur-left是否存在。if (cur-left)判断必须放在找前驱之前否则当左孩子为空时predecessor就是null再进while会直接崩。第二个是修改cur-right前必须已经通过predecessor-right把原右子树链好了。一旦你先执行cur-right cur-left原右子树就没有途径再访问到等于把数据弄丢了。很多人在递归版本里也栽跟头先展开左子树再展开右子树然后做拼接。问题是如果root-right在递归过程中被覆盖原右子树的指针就没了。所以我才特别强调旧右子树一定要单独存下来。这两个“必坑点”几乎是运行时错误的头号来源。3.3 复杂度与面试官追问在面试场景下你需要对复杂度有清晰认知。先看最简单的存数组解法时间复杂度O(n)空间复杂度O(n)。再看递归展开如果朴素版本通过while找尾最坏是O(n^2)优化为返回尾节点后时间复杂度回到O(n)但空间复杂度仍然是递归深度O(h)最坏hn时是O(n)。最后看迭代O(1)解法每个节点最多被访问两次一次是当前节点一次是作为左子树最右节点的扫描路径所以总体O(n)额外空间只有几个指针算O(1)。面试官如果问“迭代解法和上面有什么本质区别”你可以答递归和栈存储的是未来要处理的节点而O(1)迭代利用了树本身的空闲right指针作为线索相当于在遍历过程中不断改写树结构把未处理的右子树挂在已经处理完的路径末尾。这种思路和Morris遍历有异曲同工之处。4. 高频报错与排查手册4.1 最常见的三个运行时错误我身边的朋友刷这道题几乎集体踩过这几个坑。第一个是没判空比如root为null或者cur-left为空就直接访问cur-left-right立刻段错误。第二个是死循环有些版本在接链时没有断开原左孩子关系导致后续遍历时cur后退回已经处理过的节点right指针成环。第三个是结果错序比如递归版忘了保存原右子树展开后某些节点被覆盖链表长度变短。下面用一个表格把症状、原因和修正方向整理出来方便你对照排查现象根因修正方向运行时报空指针未判断cur-left是否为空就找前驱所有取left/right前先判空程序卡死或栈溢出right指针成环每次把当前节点的left置空并确保predecessor-right不会指向自身展开后少了节点原右子树没有先挂到前驱上先执行predecessor-right cur-right再执行cur-right cur-left4.2 典型错误代码复盘这里我想还原一段我最初写的错误递归void flatten(TreeNode* root) { if (!root) return; flatten(root-left); flatten(root-right); root-right root-left; // 问题就在这里root-right被覆盖了 root-left nullptr; TreeNode* p root; while (p-right) p p-right; p-right tmp; // tmp没定义 }这段代码如果运行左子树信息是保住了但右子树已经丢了。而且后面想接一个不存在的tmp编译都过不了。正确做法是先执行TreeNode* tmp root-right;把右子树保存下来再移动左子树最后把tmp接到尾节点。还有另一种隐蔽错误在迭代解法里找前驱时while循环的判断条件是while (predecessor-right)而不加predecessor非空判断。如果cur-left本身是nullpredecessor就是null直接解引用就崩了。所以if (cur-left)判断是必须的不是可有可无的防御代码。4.3 调试二叉树题目的实用技巧如果你自己写代码时老报错我建议学会给二叉树“拍照”。也就是写一个简单的层序或前序打印函数把当前节点和左右孩子值打出来。每次修改后打印一次很快就能看出哪里断了链。网上有很多可视化工具但刷题时最直接的是在关键位置加临时输出void debug(TreeNode* node) { if (!node) return; cout node-val ; debug(node-left); debug(node-right); }还有一个小习惯用最小测试用例。先测root为null再测只有一个节点然后测只有左子树、只有右子树、普通满二叉树。这道题我建议至少跑五组用例因为只有左子树的情况最容易暴露指针丢失。等你这些case全部通过再放到LeetCode上提交运行时错误的概率就会小很多。5. 这类题还能怎么延伸5.1 从展开到链表看二叉树遍历的四类应用很多读者做完114题会问学会这个有什么用其实二叉树展开为链表是“遍历顺序决定链表顺序”的一个典型例子。如果要求展开顺序是中序遍历代码会变成中序遍历版的Morris思路如果要求把二叉搜索树转换成双向循环链表LeetCode 426就是在114的基础上增加了前驱和后继两个方向的指针维护。你把这题吃透等于同时给“遍历二叉树”和“操作链表”各打了一次地基。数据结构与算法里树和链表是两种截然不同的存储结构但通过把树“重链化”能更好地理解先序、中序、后序的物理含义。之前有人问我为什么每次做二叉树的题都像在做链表其实不是错觉很多二叉树操作归根到底都是在调整指针只不过树是二维的链表是一维的。展开为链表就是把二维的树投影到一维的链上。5.2 一题多解的价值在哪回头看这道题简单解法、递归解法和O(1)迭代解法三种方案的时间和空间复杂度依次提升考察点也完全不同。简单解法考验的是基础遍历递归解法考验的是拆分问题和指针暂存能力迭代解法考验的是对前驱节点和结构改造的理解。刷题如果只追求AC那你只需要会第一种但要想真正提高我建议每道经典题都尽量写下至少两种解法并说明为什么各有优劣。我个人在实际操作中的体会是O(1)迭代解法短小精悍但不太好想。如果你第一次没想出来完全可以先用递归跑通再用递归版本去反推迭代版。递归版里先展开左子树再把左子树接到root右边本质上和迭代版的“找左子树最右节点然后把右子树接过去”是同一件事。所以不要觉得背代码有用理解两种写法之间的等价关系才是关键。最后再分享一个小技巧写完这道题后建议接着做“二叉树的中序遍历”和“二叉搜索树与双向链表”你会发现三道题之间有一条清晰的主线都是用指针调整代替新建结构。顺着这条主线练下来你的二叉树题感会在短时间内上一个台阶。