先交代个背景。我在刷力扣hot100的时候二叉树这块绕来绕去最后发现自己栽在了一道看起来并不复杂的题上144题“二叉树展开为链表”。说它不难是因为题面很直白把一棵二叉树按照前序遍历的顺序展开成一条只有右子节点的“链表”说它不简单是因为真正的难点藏在约束条件里——原地展开。很多解法第一眼看上去没问题跑测试也全绿可拿到面试官面前追问两句“空间的O(1)是从哪儿省出来的”就露馅了。这篇文章我会把这道题的前前后后拆开讲清楚包括三种从易到难的解法、它们各自的适用场景、以及我在实际刷题中踩过的一些坑。无论你是刚开始刷力扣的初学者还是已经在准备跳槽面试的老手这题都值得停下来多看两遍。1. 先把这个题目真正读明白1.1 题目在说什么一个容易被误读的“原地”LeetCode 144题原本叫“二叉树的前序遍历”但hot100里的这道“二叉树展开为链表”其实是144题的高频变体题号在不同版本里会有差异核心内容是一致的。题面给你一棵二叉树要求把它原地展开成链表展开顺序和**前序遍历先根再左再右**保持完全一致。说白了最终得到的这棵“树”每个节点只有右孩子左孩子全部为空沿着右指针一路往下走正好是前序遍历的节点顺序。我最早读到这道题的时候心里想的很直接那就前序遍历一把把节点存到数组里然后挨个改指针不就行了吗结果提交之后再看要求才发现里面有句话特别扎眼——“原地”展开。原地意味着不能另外新建一棵树不能开一个O(n)的辅助数组只能用常数级别的额外空间在原树上动指针完成变换。这一点直接把“存数组再重建”的朴素思路按在地上摩擦。这道题非常适合用来检验一个基本功你到底是真的理解二叉树前序遍历还是只会背递归模板。因为如果你真的理解前序遍历的顺序就会发现把一棵树变成一条“右链”的过程本质上是在模拟一个持续的、边遍历边改结构的操作。理解到这个层面后面的几种解法才能看懂它的精妙之处。1.2 为什么这道题值得反复做hot100之所以是hot100不只是因为面试常考而是因为它覆盖了最高频的算法思维模型。这道二叉树展开为链表表面考的是二叉树操作实际上考的是对递归返回值的设计能力怎么把“展开好了的子树的尾部”传出来对前驱/后继节点的敏感度谁在遍历顺序上是“下一个”对原地算法的理解怎么利用已有结构完成变换而不是新开空间对Morris遍历和线索二叉树的铺垫展开成右链的极致操作几乎就是Morris遍历的前半段我给不少正在准备大厂面试的朋友提过建议这题不要只看一种解法就过最好把“递归版”“迭代版”“O(1)空间版”都写一遍。原因很简单同一道题的不同解法折射出的是不同层次的思维深度。你需要做的不是背代码而是通过这道题把“树的遍历”和“指针操作”这两块能力焊死在一起。2. 解法一前序遍历之后“重新串起来”2.1 思路先采集节点再重建链表最直观的思路就是先做一次标准的前序遍历把节点按照访问顺序收集到一个容器里然后再遍历这个容器把前一个节点的右指针指向后一个节点同时把所有节点的左指针清空。class Solution: def flatten(self, root: TreeNode) - None: Do not return anything, modify root in-place instead. if not root: return nodes [] def dfs(node): if not node: return nodes.append(node) dfs(node.left) dfs(node.right) dfs(root) # 重新串联 for i in range(len(nodes) - 1): nodes[i].left None nodes[i].right nodes[i 1] nodes[-1].left None nodes[-1].right None这段代码结构非常简单任何一个会写二叉树前序遍历的人都能直接写出来。递归函数负责收集节点收集完毕之后用循环把节点串成一个右链。这里要注意几个细节第一最后一个节点的右指针一定要置为空否则它可能还挂着原来的子树第二所有节点的左指针都要清掉不然最后出来还是一堆岔路。2.2 复杂度分析时间O(n)空间O(n)时间上前序遍历每个节点访问一次后面的串联循环又访问一次所以时间复杂度是O(n)。空间上递归栈的深度在最坏情况下是O(n)更关键的是那个nodes数组额外装下了所有的n个节点所以空间复杂度是O(n)。这种解法最大的优点是好想、好写、好解释。如果你在笔试阶段看到这题用这个解法写到一半发现没报错、边界也没问题其实已经能拿到不错的基础分。但问题就出在“原地”两个字上。严格意义上的原地算法要求额外空间是O(1)除了递归栈或显式栈这里的nodes数组显然不符合。面试官如果抓住这个地方追问你就得想下一步怎么优化。2.3 这段代码里容易被忽略的坑我见过不少人在写这种解法时踩一个不大不小的坑串联循环里只改了右指针忘了改左指针。结果跑出来一看展开后的第一个节点1下面右指针确实连到了2但左指针还挂在原来的左子树上整棵树变成了一团乱麻。这提醒我们任何涉及到“修改结构”的二叉树题目改了一个指针之后一定要检查原来那些还指着旧的、不想再用的指针。还有第二个坑递归函数的空判断。如果你在递归函数里先判断if not node再return那没问题但如果你把空判断漏了直接nodes.append(node)遇到None就会把空节点也存进去串联的时候就会出现空指针访问。我建议不管题目多简单先写空树判断再写递归体。3. 解法二递归展开把左子树“塞”到右子树前面3.1 思路从子树的角度看整棵树解法一好懂但不够“树”。解法二换一个视角不是整体地做完遍历再重建而是从根节点出发递归地处理左右子树然后把左子树展开后的结果插入到根节点和右子树之间。这个过程就像是在整理一条项链先把左链整理好再把右链整理好然后把左链的末尾接到右链的开头。我们来拆解一个核心操作。假设当前节点cur的左子树已经展开成了一条右链尾部是leftTail右子树也展开成了一条右链头部是rightHead。现在要让整体变成一条右链顺序应该是cur - 左子树展开链 - 右子树展开链。所以要做的是把cur.right指向左子树链的头也就是cur.left把左子树链的尾leftTail.right指向右子树的头原来cur.right把cur.left置空。关键是怎么获取“左子树的尾”。这需要递归函数返回一个值返回当前子树展开之后它的链尾节点。有些实现里返回链尾有些实现直接用递归后再自己找尾本质是一样的。3.2 代码实现返回值设计成链尾class Solution: def flatten(self, root: TreeNode) - None: def dfs(node): if not node: return None left_tail dfs(node.left) right_tail dfs(node.right) # 把左子树放到右子树的位置上 if node.left: left_tail.right node.right node.right node.left node.left None # 返回整条链的尾部 # 优先级右子树的链尾 左子树的链尾 当前节点自身 if right_tail: return right_tail if left_tail: return left_tail return node dfs(root)我们逐行看这段代码做了什么事。递归函数先处理当前节点的左子树得到left_tail再处理右子树得到right_tail然后判断如果当前节点左子树存在把左子树链尾的right指向原右子树头部再把当前节点的right指向左子树头部也就是node.left最后清空node.left。返回值的顺序是一个容易绕晕的点如果右子树存在right_tail就是整条链路最后面的节点否则如果有左子树left_tail就是最后面的节点如果左右子树都不存在当前节点自己就是链尾。3.3 为什么这样不会丢节点许多人第一次看到这段递归的时候会很担心一个操作left_tail.right node.right这里把右子树接到左子树尾巴上那右子树原来的位置怎么办答案是——右子树原来的位置已经不需要了因为接下来node.right会被覆盖成node.left。只要在执行覆盖之前把右子树的头部保存到left_tail.right上右子树就还挂在这条链上不会被丢掉。这其实和“交换两个变量需要临时变量”是一个道理。在这个场景里left_tail就是那个临时变量它帮我们保住了右子树的引用让右子树在结构重组中不会凭空消失。理解“保存引用再覆盖”这个思路对处理所有二叉树结构修改类题目都特别有用。这种解法的缺点是递归深度依然可能是O(n)最坏情况下退化成链的树递归栈会占用O(n)的空间。所以它还不是严格意义上的O(1)空间复杂度只是比解法一的nodes数组好一些。4. 解法三找前驱节点原地完成“旋转”4.1 思路把右子树整体“送”给左子树最右边的节点现在来聊这道题最漂亮、也是面试中最容易让人眼前一亮的一种做法O(1)空间的原地展开。整体思路一句话概括——每次找当前节点左子树中“最后一个被前序遍历到的节点”也就是左子树最右边的节点把当前节点的右子树挂到这个节点后面然后把左子树搬到右边。反复执行直到当前节点为空。为什么这么做是对的呢前序遍历的顺序是“根 - 左子树 - 右子树”。当我们站在root节点时下一个要被访问的节点是左子树的根而左子树整棵访问完之后会轮到右子树。那在展开成右链的结构里左子树这条链的末尾节点它的right就应该指向右子树的根。这个“左子树链的末尾节点”恰恰就是左子树中最右下的那个节点。找到它然后把右子树接上去再把左子树挪到右边这一步就完成了“当前节点的展开”。接下来重复同样的操作只不过当前节点变为原来的左子树根。这个过程看起来像是在把整棵树一点点“掰直”最后整棵树就成了一条右链。4.2 代码实现只需要一个while循环class Solution: def flatten(self, root: TreeNode) - None: cur root while cur: if cur.left: # 找到左子树的最右节点 precursor cur.left while precursor.right: precursor precursor.right # 把右子树挂到左子树最右节点的右边 precursor.right cur.right # 左边整体搬到右边 cur.right cur.left cur.left None cur cur.right这段代码简洁得不太像一道中等题但它背后藏着的观察力才是重点。代码里的precursor就是我们要找的“前驱节点”。它从cur.left开始一路往右走直到没有右孩子为止。然后做两个操作先把整个右子树接到precursor.right上再把左子树移动到cur.right位置清空cur.left。如果cur.left为空那说明当前节点没有左子树不需要调整直接cur cur.right往下走。整个过程不需要递归不需要栈只用一个额外的指针变量空间复杂度妥妥是O(1)。4.3 为什么是O(1)空间它到底在做什么很多人看到“O(1)空间”会觉得很神奇但其实它和Morris遍历是同一套思路通过修改树中空闲的右指针来记录后继节点从而不需要额外的栈空间来保存回溯信息。Morris遍历的核心思想就是利用叶子节点的空余指针让遍历过程能够回到祖先节点。而这道题的“找左子树最右节点把右子树接上去”本质上就是Morris遍历里“建立临时线索”那一步。如果你之前接触过线索二叉树Threaded Binary Tree再来看这段代码会特别有感觉。线索二叉树就是利用空余指针保存前驱或后继而这里的操作是借用左子树最右节点的空right指针来“预告”右子树的位置然后再通过结构变换真正把右子树挪过来。所以说这题不仅仅是刷题它是通往Morris遍历的一座桥梁。4.4 手推一个例子别被绕晕为了讲清楚这个过程我拿一个经典例子手推一遍。假设初始树是1 / \ 2 5 / \ \ 3 4 6前序遍历结果是1, 2, 3, 4, 5, 6。现在用解法三来展开。第一步cur 1。cur.left存在找到左子树根为2的最右节点4。然后把cur.right5为根的树接到precursor4的右边即4.right 5。接着cur.right cur.left即2cur.left None。此时树变成1 \ 2 / \ 3 4 \ 5 \ 6注意3还是2的左孩子还没处理。第二步cur cur.right 2。cur.left 3存在找到左子树3的最右节点就是3本身。然后把cur.right从4开始的右链接到precursor3的右边即3.right 4整个4-5-6链都带过去了。接着cur.right 3cur.left None。树变成1 \ 2 \ 3 \ 4 \ 5 \ 6到这一步整条右链刚好就是前序遍历顺序1, 2, 3, 4, 5, 6。后面cur继续往右走每个节点都没有左孩子循环无事发生最后退出。这个手动推演的过程非常重要。我建议看这篇文章的你也拿纸笔画一遍——不是复制我这段而是自己随便构造一棵树然后按代码逻辑一步步改指针。很多二叉树操作画一遍胜过看十遍。5. 三个解法摆在一起怎么选5.1 复杂度与适用场景对比解法时间复杂度空间复杂度代码量面试表现力解法一前序数组O(n)O(n)最少一般解法二递归返回链尾O(n)O(n)递归栈中等良好解法三找前驱原地O(n)O(1)中等最佳从刷题的角度三种解法都能过测试。但从面试的角度你至少要能写出解法二或解法三。解法一更适合作为“热身理解题意”的思路——先把最朴素的解写出来确认样例通过再告诉面试官“这个解法空间复杂度是O(n)我继续优化一下”。解法二适合展示你“以递归的视角看待树结构变化”的能力解法三适合展示你对遍历顺序的深层理解和对指针操作的把握。实际面试中如果面试官追问“能不能用O(1)空间做出来”解法三就是标准答案。5.2 面试时怎么讲才能拿到高分我给几个实际建议。第一面试时不要上来写码先画图。把一棵示例树画出来标出前序遍历顺序然后指着图说自己打算怎么做。这样面试官能直接看到你的思路是否清晰。第二解法的关键环节要在代码里用注释标出来尤其是“找到左子树最右节点”这一步很多人写代码能过但讲不出来为什么找最右节点。能讲出来就已经赢过大多数人。第三主动分析复杂度尤其是解释解法三为什么空间是O(1)——因为它没有用任何递归或栈只是几个指针在原有树上移动。6. 刷这道题我踩过的坑以及定位技巧6.1 最经典的坑死循环解法三最常见的问题是写完代码后一运行就超时陷入死循环。原因多数出在“cur推进”这一步。很多人写完if cur.left:的调整逻辑之后忘了在else分支里让cur cur.right或者更隐蔽的问题——因为把右子树接到precursor右边之后cur.right已经被换成了左子树如果此时接下来还取cur.right会导致某些节点被重复处理或形成环。解法三里cur cur.right这行一定要放在if cur.left:块的外面。原因在于不管当前节点有没有左子树处理完之后我们都应该向右走因为左子树已经被搬到了右边或者本来就没有。6.2 丢节点顺序错了整个右子树没了还有一个很容易踩的坑是操作顺序。解法三里必须先执行precursor.right cur.right再执行cur.right cur.left。这两个顺序不能颠倒。如果先执行了cur.right cur.left那么原来的右子树就丢失了除非你用临时变量先保存了它再想接到precursor后面就晚了。我见过一些人在这一步翻车然后debug半天找不到问题。其实从引用的角度理解就很清晰——precursor是原左子树里的节点cur.right被覆盖前必须先把它保存到一个仍然可达的位置。precursor.right就是那个位置。6.3 递归深度的隐患解法一和解法二都用了递归在极端情况下树退化成一条链递归深度是n栈溢出风险还是存在的。力扣上大部分测试用例不会给你弄一个10万层深的树但如果是本地做压力测试或者在实际工程里遇到类似场景就要考虑迭代或者解法三这种无递归的方案。当然递归在二叉树操作里依然是思维最直观的工具我并不是说递归不好——只是你应该知道它的边界在哪里。6.4 怎么设计自己的测试用例写完代码之后不要只跑题目给的例子。我习惯自己构造至少五组用例空树root None应该直接返回None不报错。只有一个节点展开后就是它自己左右都为空。只有左子树的链比如1 - 2 - 3这种左链展开后应该变成1右2右3。只有右子树的链比如1 - 2 - 3这种右链展开后保持原样。完整二叉树像我上面推演的那棵树重点看无序性比较强的。这五组用例基本覆盖了边界条件和结构变化的核心场景。刷二叉树题的时候养成自己造用例的习惯比多刷十道题还有用。7. 从这道题往外延伸它还能带出什么7.1 和线索二叉树的关联上面已经说过解法三的本质就是线索二叉树的建树思路。线索二叉树Threaded Binary Tree在传统的二叉树基础上把空的左指针或右指针利用起来分别指向遍历序列中的前驱或后继节点。展开为链表这道题等于把树的全部右指针都变成“线索”指向后继节点而左指针全部置空。理解了这一点再去看时间复杂度O(n)、空间O(1)的Morris前序遍历会非常轻松。Morris遍历的代码往往看起来“很难记”其实就是因为你先没有理解它背后的那根“线索”。如果你把二叉树展开为链表的解法三吃透了Morris遍历的“临时线索建立”部分你就已经理解了一半。7.2 变体问题中序展开、后序展开怎么办如果把题目改成“按中序遍历顺序展开为链表”或者“按后序遍历顺序展开”解题思路会有什么变化中序展开时要找的不再是左子树最右节点而是左子树中最右节点还是最左节点我们按中序顺序去推理中序是“左 - 根 - 右”站在根的角度前驱应该是左子树最右节点后继是右子树最左节点。如果想把根放在左右子树链的中间结构变换会更复杂通常需要用递归返回链头和链尾两个信息来解决。这样去推理变体有一个好处——你不再背题目而是在真正地理解遍历顺序。很多面试题都是基础题的包装底层的思维模型不会变。7.3 嵌入式二叉树内存受限场景下的紧凑存储最近看到有人讨论“嵌入式二叉树”这个概念。在嵌入式环境中内存极度受限动态分配节点和递归遍历都可能成为负担。把二叉树展开成链、再退化成数组存储是很多嵌入式数据结构的常见做法。原因很简单链式存储每个节点要额外保存两个指针16字节或24字节没了而展开成右链之后每个节点只需要一个后继指针再配合数组索引内存占用可以压缩不少。这和二叉堆的思想是一致的——二叉堆用数组存储完全二叉树不存指针靠下标计算父子关系。不过二叉堆要求树是完全二叉树而“展开为链表”适用的树范围更广代价是丢失了随机访问父子关系的能力只能顺序遍历。工程上具体用哪种取决于你的核心操作是“查找父子”还是“顺序遍历”。7.4 力扣hot100之外这题在真实面试里的微妙之处我在帮朋友模拟面试的时候经常把这道题作为二叉树环节的“压力测试题”。原因在于它不像动态规划那样有大段的状态转移但同样能试探一个人的基本功扎不扎实。你做出来了面试官会继续追问递归栈的空间算不算额外空间如果算你怎么做到O(1)如果你能接住这些问题说明你对“原地算法”的理解是到位的对“树的遍历”的理解也远超背模板的水平。刷力扣这件事大家的目的都很明确想进大厂、想在面试中展现出扎实的算法功底。hot100题的意义不在于你刷了多少遍而在于你是不是真的把每一道题的解法从“背下来”变成了“理解透”。二叉树展开为链表这道题恰好是检验这个分水岭的好题目。8. 一点实操心得我自己在刷这道题的过程中最大的收获不是记住了解法三的代码而是养成了一个习惯任何二叉树结构修改类的题目动手写代码之前先画图推演一遍指针变化的顺序。这个习惯帮我避免了很多调试时间。特别是像“先接右子树再接左子树”这种顺序问题画一遍图你永远都不会忘。另外这道题我建议你用至少两种语言各写一遍。比如用Python写一遍再用C写一遍。不是故意折腾自己而是因为C的指针操作更接近底层能逼你把“引用”“节点替换”这些概念想得更具体。什么时候体会到了“precursor.right cur.right”这行代码对内存的真实改动你就真的懂这道题了。如果后续你准备刷Morris遍历相关的内容或者想挑战一下“二叉树展开为链表”的变体题把今天这篇里的解法再三好好理解一遍你会发现自己上手会快很多。这大概就是hot100题的价值所在——它不是在考你一道孤立的题而是在帮你搭一座知识之间的桥。