LeetCode 114：二叉树展开为链表的原地O(1)算法详解-北京尧图网络

1. 题目到底在考什么1.1 题面拆解不是“压扁”是前序遍历重连力扣第114题《二叉树展开为链表》的题面很短但信息量一点不少给定一棵二叉树要求原地把它展开成一个链表链表顺序必须是前序遍历顺序展开后每个节点的 left 指针都要置空right 指针指向链表中的下一个节点。举个例子给一棵这样的二叉树1 / \ 2 5 / \ \ 3 4 6原树的层序遍历结果是[1,2,5,3,4,null,6]而题目要求的输出是[1,null,2,null,3,null,4,null,5,null,6]。我第一次看到这个输出的时候也愣了一下为什么好端端的链表里全是 null后来才反应过来这里的 null 是序列化层的产物用来表示每个节点的 left 子树为空。真正用 right 指针串出来的链表是1 - 2 - 3 - 4 - 5 - 6所以别被示例输出里的 null 绕晕题目的本质很简单把一棵二叉树的前序遍历结果用节点自带的 right 指针串成一条单链表同时把所有 left 指针清空。这类题在力扣热题100里经常被归到“二叉树”和“链表”的交界处。你说它是二叉树题吧最后输出的结构又完全是单链表你说它是链表题吧中间所有递归、遍历、指针处理又全是二叉树的老套路。正是这种交叉性质让它成了面试里特别爱考的一题。1.2 “原地”两个字才是重点题目里还有个容易被忽略的限制原地。意思是不能 new 一棵新树不能复制节点只能在这棵二叉树上改指针。很多人第一次写这题直接前序遍历一遍把节点塞进数组再重新串一遍也能过。但这样做严格来说并不是原地因为额外用了一个长度为 n 的数组。面试官如果深究下去往往会追问一句“能不能把空间复杂度降到 O(1)”到这一步才是这题真正拉开差距的地方。所以我的看法是这题至少要掌握两套解法。第一套是常规的递归或迭代解法用来保证你快速 AC第二套是 O(1) 空间的循环解法用来应对“原地”这个要求的终极版本。下面我按从易到难的顺序把三种写法全部拆开讲一遍。2. 三种主流解法先易后难2.1 解法一前序遍历存数组再重新串起来这是最直观的思路先做一次前序遍历把节点指针按顺序存进 vector然后遍历这个 vector把每个节点的 left 置空right 指向下一个节点。C 代码长这样class Solution { public: void flatten(TreeNode* root) { vectorTreeNode* nodes; preorder(root, nodes); for (int i 0; i (int)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); } };这个解法最大的优点是好懂不容易写错。前序遍历的顺序就是展开后链表的顺序只要保证节点指针在 vector 里的排列顺序正确后面串链表的部分闭着眼睛都能写完。但它的问题也很明显额外开了 O(n) 的空间。如果题目要求严格原地这个写法过不了面试官的追问。而且因为要先把整棵树遍历完再重建树的规模一大内存占用也会跟着涨。所以我的建议是这个解法用来“保底”可以用来“说服面试官”不够。你至少要能从这里过渡到递归拼接或迭代栈的写法。2.2 解法二递归后序先让子树各自展开再拼接递归解法里我推荐后序而不是前序。原因很简单在把左子树“插”到根节点和右子树之间之前你必须先保证左子树和右子树都已经各自展开成了链表。这正好是后序遍历的顺序先处理左子树再处理右子树最后处理当前节点。先看完整代码class Solution { public: void flatten(TreeNode* root) { if (!root) return; // 先让左右子树分别展开成链表 flatten(root-left); flatten(root-right); TreeNode* left root-left; TreeNode* right root-right; if (left) { // 找到左子树展开后的链表的尾节点 TreeNode* tail left; while (tail-right) { tail tail-right; } // 把原来的右子树接到左子树链表的末尾 tail-right right; // 把左子树整体挂到 root 的右边 root-right left; // 左指针置空 root-left nullptr; } } };这段代码的关键是理解三个指针各自该往哪放left当前节点的左子树展开后应该成为当前节点的下一个节点所以root-right left。right当前节点的右子树展开后应该跟在左子树整条链表的后面所以要先找到左子树的尾节点tail再tail-right right。root-left最后必须置空否则整棵树的结构就不是单链表。很多人第一次写会犯同一个错误递归处理完左右子树之后直接写root-right root-left结果发现原来的右子树丢了。原因是你没有先把right存下来或者没有把它接到左子树尾部。正确的顺序一定是在修改root-right之前先把右子树指针保存好并把它接到tail的后面。这版的递归栈深度是 O(h)其中 h 是二叉树的高度。对普通二叉树来说没问题但如果树退化成了一条链递归深度可能到 O(n)极端情况下有爆栈风险。2.3 解法三迭代加栈模拟前序遍历但不用数组如果用递归代码简洁如果不想用递归可以用一个栈来模拟前序遍历。思路是每次从栈里弹出一个节点把它当成当前链表节点处理然后把它的右孩子、左孩子依次压栈保证下一次弹出的节点是前序顺序里的下一个节点。代码class Solution { public: void flatten(TreeNode* root) { if (!root) return; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* cur st.top(); st.pop(); // 栈是后进先出所以先压右孩子再压左孩子 if (cur-right) st.push(cur-right); if (cur-left) st.push(cur-left); if (!st.empty()) { cur-right st.top(); } else { cur-right nullptr; } cur-left nullptr; } } };这个写法和解法一的本质其实是同一个都是模拟前序遍历。区别只在于解法一把所有节点都存进数组再串解法二边遍历边串节省了 vector 的开销。但要注意栈在最坏情况下也需要 O(n) 的空间所以它也不是严格意义上的 O(1) 原地算法。写这个解法时最容易错的地方是压栈顺序。因为栈是后进先出想按“根 - 左 - 右”的顺序弹出就必须先压右孩子再压左孩子。如果顺序写反链表顺序会变成“根 - 右 - 左”一提交就是 Wrong Answer。3. 真正原地的高阶写法O(1) 空间的循环改造3.1 为什么还要学 O(1) 写法力扣很多题解用上面的递归或迭代就能过但如果你细心看题目里“原地”两个字会发现面试官想听的其实是 O(1) 空间的写法。尤其是一些大厂面试会把这题当作二叉树遍历和指针操作的组合题来考聊到最后基本都会追问一句“能不能不用递归和栈”这时候就需要祭出和 Morris 遍历类似的思路利用树中空闲的 right 指针来记录后继信息一边遍历一边改结构最后把所有 left 指针清空。下面这种写法空间复杂度是 O(1)时间均摊 O(n)是真正能答到点子上的版本。3.2 核心思想把左子树当作“插队”的一部分先想清楚前序遍历的顺序根节点 - 左子树全部节点 - 右子树全部节点。如果当前节点cur有左子树那么在前序顺序里左子树的所有节点都应该排在cur和cur的右子树之间。所以我们可以做这样一件事找到左子树展开后的最后一个节点把它和原来的右子树接起来再把整个左子树搬到cur的右边。具体分三步找到cur-left这条链上的最右节点tail。把原来的右子树接到tail的后面tail-right cur-right。把左子树整体挂到右边cur-right cur-left同时cur-left nullptr。处理完当前节点后把cur移动到cur-right继续处理下一个节点。重复这个过程直到cur为空。这个过程可以想象成每个节点都把自己手头的一支“左路队伍”插到“右路队伍”前面插完之后左边就空了然后顺着新形成的右链继续走。最终整棵树就成了一条按前序排列的单链表。这种写法其实就是 Morris 遍历思想的变体。Morris 遍历的核心是利用空闲指针建立临时线索在遍历完成后可以还原二叉树这里虽然不需要还原但“找左子树最右节点”这一步和 Morris 是一模一样的。理解了它你再看线索二叉树相关的题会顺很多。3.3 代码实现C 和 Python 版本C 版本class Solution { public: void flatten(TreeNode* root) { TreeNode* cur root; while (cur) { if (cur-left) { // 找到左子树中的最右节点 TreeNode* tail cur-left; while (tail-right) { tail tail-right; } // 把原来的右子树接到左子树尾部 tail-right cur-right; // 把左子树整体搬到右边 cur-right cur-left; cur-left nullptr; } // 继续处理下一个节点 cur cur-right; } } };Python 版本class Solution: def flatten(self, root: Optional[TreeNode]) - None: cur root while cur: if cur.left: tail cur.left while tail.right: tail tail.right tail.right cur.right cur.right cur.left cur.left None cur cur.right这个代码很短但每一步都有讲究。尤其是tail-right cur-right这行必须放在cur-right cur-left之前否则cur-right已经被覆盖成了左子树原来的右子树就找不到了。3.4 复杂度和正确性分析时间上每个节点最多被“找 tail”的逻辑访问常数次。虽然我们会在每个有左子树的节点上都向下去找最右节点但这些路径大多会在后续处理中变成已经展开好的右链不会再被重复扫描所以整体是均摊 O(n)。空间上整个过程只用了一个cur和一个tail指针额外空间 O(1)是真正的原地写法。为什么它最后的结果一定是前序顺序可以这样理解每轮操作都把当前节点的左子树整体移动到右子树之前等价于把前序序列里的“左子树块”搬到正确的位置。每处理一个节点这个节点和它的左子树块就被固定到最终顺序里不会再被破坏。循环结束后所有 left 指针都置空整棵树变成了一条只有 right 指针的单链表。4. 写完代码之后的那些坑4.1 递归解法最容易丢数据没先保存右子树在递归拼接解法里最常见的错误是这样flatten(root-left); flatten(root-right); // 找到左子树尾节点 TreeNode* tail root-left; while (tail-right) tail tail-right; root-right root-left; // 这一步把原来的右子树覆盖了 tail-right root-right; // 这时候 root-right 已经不是原来的右子树了这个代码的问题在于root-right已经被改成了左子树再去访问root-right拿到的自然是左子树原来的右子树在那一步就已经丢了。解决办法很简单在一开始就把左右子树分别存到局部变量里后续操作只操作局部变量。4.2 迭代法压栈顺序写反链表顺序变成中序用栈模拟前序遍历时一定要记住栈的特性是后进先出。想要弹出顺序是“左孩子在右孩子前面”压栈的时候就必须“右孩子先进左孩子后进”。很多新手朋友习惯先写if (cur-left) st.push(cur-left);结果链表顺序变成先右后左一跑测试用例就错。另外有些版本的迭代解法会在弹栈时直接修改cur-right st.top()但需要注意如果当前节点没有孩子栈可能为空。此时要显式地把cur-right置空否则它可能还保留着原来的右孩子导致链表末尾多出一截。4.3 O(1) 写法里最容易出的问题找错 tailO(1) 写法虽然短但while (tail-right)这一步很容易被写错成while (tail-left)或者忘记写 while只判断一层。如果忘记循环只把左子树根节点的右指针接到原右子树上那么左子树更深层的节点就会断链最终输出缺失一部分节点。调试时我习惯先用一个辅助函数把当前 right 链打印出来void printFlatten(TreeNode* root) { while (root) { cout root-val; if (root-right) cout - ; root root-right; } cout endl; }然后再跑几个小样例对比输出的顺序是不是和手工前序遍历一致。这个方法特别适合排查那种“只错一个节点”的隐蔽 bug。4.4 常见问题速查表现象可能原因解决办法展开后顺序是根、右、左迭代法压栈顺序反了先压 right再压 left整棵右子树消失没有保存原 right 指针或拼接顺序错误先用变量保存 right再修改 cur-right链表末尾多出一截旧结构left 没置空或 cur-right 没在栈空时置空每个节点都显式 left nullptr栈空时 right nullptrO(1) 写法结果少节点找 tail 只判断了一层没有 while 循环到底确认while (tail-right)能走到最右节点递归爆栈输入树退化成链递归深度 O(n)改用迭代或 O(1) 循环版本4.5 一个调试心得拿小树手推指针每次写这类树结构修改题我都会先画一棵只有三个节点的最小树根节点、左孩子、右孩子。然后在纸上把递归和迭代两种写法的指针变化走一遍。比如根节点是 1左子树是 2右子树是 3。手动推一遍递归版本要先展开 2 和 3再把 2 接到 1 的右边3 接到 2 的右边O(1) 版本要先找左子树尾节点 2把 2 的右指针指向 3再把 1 的右指针指向 2。走完这两个流程你对这题的把握会立刻超过只抄答案的人。5. 从这题延伸出去线索二叉树和更多变体5.1 中序展开和后序展开变体力扣 114 要求的是前序遍历顺序但很多面试官喜欢顺手问一句“如果要求按中序遍历展开成链表呢”思路其实一模一样换一种遍历顺序仍然用递归或栈来处理区别只是节点串起来的时机。如果是中序展开可以把整棵树的中序遍历结果存进数组再重建也可以用一个全局的last指针在中序遍历的过程中边访问边串链表。后序展开同理唯一需要牢记的是遍历顺序决定拼接顺序其他操作完全一致。5.2 线索二叉树和 Morris 遍历的血缘前文提到 O(1) 解法用到了 Morris 遍历的思想。如果想彻底弄懂这类操作我建议去了解一下线索二叉树它利用空余的 left 和 right 指针分别指向遍历顺序中的前驱和后继从而让一次遍历不需要递归或栈。线索二叉树通常用于中序遍历构造时也是“找左子树最右节点把它的右指针指向当前节点”这一套。所以你会发现力扣 114 的 O(1) 解法其实就是在把二叉树改造成一种“临时线索链表”只不过最后把所有 left 置空只保留 right 线索。理解了这层关系再遇到二叉搜索树转双向链表之类的问题你会更容易看出套路。5.3 复杂度对比面试时这样答最加分解法时间复杂度空间复杂度是否严格原地前序遍历存数组再重建O(n)O(n)否递归后序拼接O(n)O(h)否含递归栈迭代栈模拟前序O(n)O(h)否O(1) 循环改造均摊 O(n)O(1)是面试时我建议这样递进先抛出最直观的数组解法确认顺序理解正确然后说“我可以不用额外数组改成递归拼接”接着补一句“如果要求严格 O(1)还可以用类似 Morris 遍历的思路在遍历过程中直接把左子树搬到右边”。这样一层层递进面试官能清楚看到你对二叉树遍历、递归栈、指针操作的理解程度。5.4 不同语言的写法细节C 版写指针时要注意TreeNode* left root-left这类局部变量别把指针别名搞混Python 版写Optional[TreeNode]时要注意cur.left的判空逻辑代码反而比 C 更简洁。无论用哪种语言真正重要的是理解“左子树整体插到右子树前面”这个动作代码只是把这个动作翻译出来而已。最后再分享一个小技巧我自己刷这题的时候最受益的一个习惯是每写完一种解法都去 LeetCode 官方题解的评论区找一个“为什么这样写”的追问而不是只看 Accepted。比如 O(1) 解法里那行tail-right cur-right表面上是把右子树接到左子树尾部实际上是在维护前序序列的连续性。如果只看代码不看思想下次换个题目出照样不会写。这题和链表反转、二叉树最近公共祖先一样属于“思路不难细节很多”的经典题。建议你至少把递归后序和 O(1) 循环两种写法练到默写程度再顺手用中序展开当扩展练习。刷完这题之后再去看括号生成、二叉树序列化这类题目你会明显觉得自己的递归和指针操控能力上了一个台阶。

LeetCode 114：二叉树展开为链表的原地O(1)算法详解

相关推荐

Wine运行器实战指南：图形化封装让Linux跑Windows程序更简单

OpenClaw与SaaS的Skill化：智能体如何重塑软件交互

二维前缀和与子矩阵求和：从暴力遍历到O(1)查询的优化实战

更多资讯

BUUCTF Web第二页实战：文件包含、伪协议与上传绕过全解析

Linux软件安装全攻略：依赖解析、容器化、源码编译与多版本管理

云桌面玩主机游戏实战：从部署到调优的完整指南

Blender粒子头发导出UE5 Groom全流程：从梳理到材质渲染的实战指南

JDBC执行多条SQL的三种方式：批处理、多语句与存储过程

用Python与XGBoost实现二分类：从数据预处理到模型上线

今日更新

PHP htmlentities()函数用法讲解

AI Agent工程实战：从七要素到七个决策点的系统设计指南

AI入局芯片设计验证：验证收敛50倍加速的真相与应对

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？