1. 这道hot100题到底在考什么先序遍历与“原地”两个关键词LeetCode 114题“二叉树展开为链表”在hot100里的位置很特殊。它看起来不像难题却拦住了大量刷题的人——我见过不少能轻松写出二叉树层序遍历的选手在这道题上反复提交四五次才通过。原因在于题目本身带有两个容易忽略的关键词先序遍历顺序和原地展开。先看题目要求给定一棵二叉树将它展开为一个单链表展开后的单链表应该与二叉树先序遍历顺序相同。具体到数据结构上展开后的“链表”依然沿用TreeNode结构left指针全部置空right指针作为next使用最终形成一条从根节点开始的右指针链。很多人的第一反应是“这有什么难的先序遍历一遍存到数组里再串起来不就完了”。这个思路完全正确但题目里有个隐藏的进阶要求——原地展开也就是不能使用额外的链表、数组或其他数据结构来存储中间结果。如果只是遍历后重建时间复杂度和空间复杂度都会变成O(n)虽然能通过但完全没有触及这道题真正想考察的能力。展开后节点顺序等于先序遍历顺序意味着根节点在最前然后是左子树的全部节点接着才是右子树的全部节点。树的右指针链要完全等价于先序遍历序列。这就要求我们在操作指针时既不能丢失右子树的引用又不能破坏尚未处理的节点关系。我觉得这道题之所以被选入hot100恰恰因为它是“二叉树”和“链表”两个高频考点的交叉地带。面试官特别爱用这道题来考察候选人对指针操作的理解深度——你写的代码能不能做到时间O(n)、空间O(1)你能否在不借助辅助结构的前提下只靠调整指针完成结构转换这两个问题直接区分了“背过题解”和“真正理解数据结构”的人。2. 递归解法最容易写对也最容易在空间上翻车2.1 最容易想到的全局前驱写法如果没有任何前置知识大部分人第一版代码会写成这样class Solution: def flatten(self, root: TreeNode) - None: self.prev None def dfs(node): if not node: return # 保存右孩子因为接下来要修改指针 left, right node.left, node.right if self.prev: self.prev.right node self.prev.left None self.prev node dfs(left) dfs(right) dfs(root)这段代码的核心思路是维护一个prev指针记录上一次访问的节点。每遍历到一个新节点就把prev的right指向当前节点同时把prev的left置空。实话说这段代码能跑通大部分测试用例但存在两个隐患。第一个隐患是空间复杂度不满足进阶要求——递归深度等于树高最坏情况下退化成链的树递归栈深度是O(n)这不叫严格意义上的原地。第二个隐患更隐蔽如果你在递归左子树之前先保存了right但实际上并没有把node.left置空后面展开时左子树就可能残留引用导致结构错误。上面代码里通过统一置空left规避了这个问题但很多人写的时候会漏掉。我最初刷这道题时也写过类似版本提交一次被一个用例打回来输入是[1,null,2,3]输出变成了[1,2,null,null,3,null]仔细检查才发现是递归顺序和指针操作配合出了问题。2.2 后序变形的正解版本递归的另一种经典写法是后序处理——先把左右子树都展开成链表再把右子树接到左子树链表的末尾最后把整个左子树链挪到根节点的right位置。这种思路更符合“分治法”直觉class Solution: def flatten(self, root: TreeNode) - None: if not root: return self.flatten(root.left) self.flatten(root.right) # 左右子树都已经展开成链表 left_head root.left right_head root.right if left_head: # 找到左子树链表的末尾 tail left_head while tail.right: tail tail.right # 把右子树链表接到左子树链表末尾 tail.right right_head # 把左子树链表放到root右边 root.right left_head root.left None # 如果左子树为空右子树已经展开无需额外操作这种写法在逻辑上更直观既然题目要求展开结果是“根 - 左子树展开结果 - 右子树展开结果”那就递归地把左、右子树分别变成链表再拼接。关键操作是找到左子树链表的尾节点然后把右子树的链表头接上去。这段代码在LeetCode上能通过全部用例但它同样是递归实现最坏情况空间复杂度O(n)。而且找左子树尾节点需要一次遍历所以每个节点被访问多次时间复杂度虽然是O(n)但常数不小。2.3 递归写法的复杂度账本把两笔账算清楚就能理解为什么题目要求O(1)空间是合理的时间维度每个节点最多被访问常数次总体O(n)。不管哪种写法树的规模决定了必须遍历所有节点这一步无法省。空间维度递归栈消耗取决于树高。完全二叉树树高O(log n)退化链树树高O(n)。如果面试官追问“最坏情况空间复杂度”你要能意识到递归在这里不是最优雅的选择。从实际刷题角度我建议把递归写法当作“理解题意的工具”而不是“最终答案”。它能帮你确认先序遍历顺序和指针展开的正确逻辑但不要停在递归这层——要继续往下看前驱节点法。3. 前驱节点法O(1)空间的“拉直”操作3.1 核心思想把右子树挂到左子树的最右节点下递归方案本质上做了“先改子树再合并”的工作。那么能不能在遍历的同时直接完成展开不借助额外空间可以。关键是利用一个从Morris遍历中借鉴来的思想右指针链就是“线索”。Morris遍历能实现O(1)空间的二叉树遍历核心就是利用空闲的right指针作为线索回指祖先节点。这道题的flatten操作可以利用类似思路只不过目标不是回指而是把整棵树的right指针链排列成先序顺序。直白地说算法只需要做一件事每遇到一个“有左子树”的节点就找到左子树先序遍历的最后一个节点也就是左子树的最右节点把这个最右节点的right指向当前节点的right然后把当前节点的right指向当前节点的left并把left置空。用生活类比来解释想象一个长长的队伍你站在队首。你的左手边站着一排人左子树右手边也站着一排人右子树。要求最后排成一条沿右手方向的单列队伍。做法是先从你左手边这一排的最后一个人开始让他拉上你右手边那一排的第一个人然后你转身让右手边直接拉上你左手边这排的第一个人。于是一个队列就接起来了。整个过程不需要临时找一块空地让大家重新排队——所有人只是换了一下牵手对象。3.2 标准实现完整可运行的Python代码class Solution: def flatten(self, root: TreeNode) - None: Do not return anything, modify root in-place instead. cur root while cur: if cur.left: # 找到左子树的最右节点 predecessor cur.left while predecessor.right: predecessor predecessor.right # 把右子树接到左子树最右节点下面 predecessor.right cur.right # 把左子树搬到右边 cur.right cur.left cur.left None # 继续处理下一个节点 cur cur.right这是我最推荐的标准写法。代码量很小但它包含了几个容易写错的地方我在第4节会详细展开。先梳理一下它为什么能工作cur指针从根节点出发沿right方向移动。每次循环处理一个节点。如果当前节点没有左子树说明它的右子树已经是正确顺序的一部分直接cur cur.right。如果当前节点有左子树需要做一次“搬迁”把整个右子树挂到左子树的最右节点后面。为什么是最右节点因为左子树的先序遍历序列中最右节点是左子树的最后一个节点——先访问完左子树全部节点后接下来才该访问右子树。这个过程中cur本身不需要移动回左子树——因为我们已经把左子树通过right指针接在cur.right上了cur cur.right就自然进入了左子树的第一个节点原来的左孩子。3.3 为什么这种写法不会破坏树操作顺序的保证“不会破坏树”听起来很玄乎其实核心是在修改任何指针之前必须保证信息已经在新的引用体系里可到达。看predecessor.right cur.right这一步。执行它之前cur.right还被cur引用着执行之后虽然cur.right的父指针指向变了但通过predecessor依然能到达整棵右子树。此时即使cur.right紧接着被覆盖右子树也没有丢失。再看cur.right cur.left这一步。执行它之前cur.left和cur.right的内容都已经被预先安排好了左子树在cur.left下右子树已经被挂在左子树最右节点的右侧。执行完这一步左子树变成当前节点的右子树left置空。从当前节点的视角看它的左右子树信息都完整保留在新的right链上。关键不变量循环过程中从cur出发一直沿right走访问的序列恰好是当前已处理部分应该呈现的先序遍历前缀而每个节点的左孩子要么为空要么已经被处理完不会产生干扰。这个不变量保证了算法结束时整条right链就是完整的先序遍历序列。4. 边界样本与手撕细节这些坑我调试时才真正发现4.1 空树与单节点看似没问题实际最容易翻车我在第一次手撕这段代码时总觉得“空树返回空单节点返回自身”这样简单的边界不会出错结果真就出错了。原因是cur cur.right这行放在循环体最前面如果root是None进入循环体直接访问cur.left就会抛空指针异常。正确的处理很简单while cur这一行天然跳过了空树。但很多人写的时候会把循环条件写错或者额外加一个if not root: return——这当然没错只是不够优雅。单节点的情况cur.left为None跳过搬迁操作cur cur.right变成None循环结束结果正确。但这里面有一个更隐蔽的问题如果根节点的左子树为空但右子树非空会不会漏处理不会。因为cur.left为空代码把cur cur.right直接去处理右子树第一个节点了。右子树此时是未展开的原始子树继续循环就能展开。我建议大家在本地测试时至少跑三组用例[]、[1]、[1,2,5,3,4,null,6]题目标准示例。这三组能覆盖空树、单节点、完整左右子树三种情况。4.2 左子树成链的情况前驱查找的终止条件这个坑是最常见的报错来源。看这段查找前驱的代码predecessor cur.left while predecessor.right: predecessor predecessor.right如果左子树本身就是一条右链例如左边只有右孩子一路到底这个循环会一路走到最末尾正好是左子树的最后一个节点。然后把这个节点的right指向cur.right完成拼接。但如果左子树非常深且每个节点都有右子树这个查找过程会耗费O(树高)时间。结合外层循环整体时间复杂度会不会退化成O(n^2)这是面试中容易被追问的点。答案是不会。注意一旦我们把左子树搬到右边cur就会沿着新挂接的链快速前进而已经处理过的节点不会再次被当作“左子树存在”的节点处理。每个节点的right指针最多被修改两次一次是拼接一次是搬移总操作次数是O(n)平均到每个节点就是O(1)。虽然某个特定的“找前驱”操作可能比较长但整体摊还下来效率依然很高。如果用的是Java或C需要注意判断predecessor.right时会不会修改到cur.right本身。不会因为在拼接操作执行之前cur.left和cur.right是两棵互不相交的子树predecessor只会在左子树内部移动。4.3 常见的七种错误写法对照表我把过去刷题时看到过、自己也犯过的错误整理成一张表错误类型错误示例后果忘了predecessor.left也是非空只找predecessor.right没注意left链拼接位置错误整条链顺序乱先搬移左子树再接右子树先执行cur.right cur.left再找predecessor左子树链的末尾丢失无法找到真正的最右节点没有把cur.left置空搬移后left还指向原左孩子树结构残留环/多路径遍历时重复访问把predecessor写成cur.left直接t cur.left就拼接如果左子树不止一个节点则右子树被错误地接到左子树的根节点上递归时没有先处理右子树先递归左子树再递归右子树左右子树互相干扰展开结果错误用额外数组存储遍历list.append后重建链表空间O(n)不满足进阶要求把右子树接到左子树最右节点后忘记更新curcur不动死循环提交超时这七种错误里第二种最危险——顺序反了以后程序不会立刻报错但展开结果会变成一个奇怪的交错结构很难调试。我的经验是拿到这道题先在纸上走一遍[1,2,5,3,4,null,6]的完整流程把每一步的指针变化画出来比直接写代码更高效。5. 从114到hot100同源题一个套路打穿一串题5.1 二叉树的遍历与线索化思想迁移刷完这道题我最大的收获不是掌握了某一段代码而是对“线索化”这个概念有了直观理解。线索二叉树的本质就是利用树的空指针来保存某种遍历顺序下的前驱/后继信息。114题所做的本质上就是“把每个节点的后继关系显式化”的过程。基于这个理解很多hot100里的题是可以串联起来的94题二叉树的中序遍历进阶要求同样是O(1)空间标准解法就是Morris中序遍历。你会发现Morris中序遍历里“找cur的前驱节点”这段代码和114题里“找左子树最右节点”几乎一模一样。105题从前序与中序遍历序列构造二叉树依赖的是先序/中序序列的性质。做114题时你对先序遍历的理解会加深反过来有助于理解105题的切割逻辑。98题验证二叉搜索树中序序列递增的判定也可以用Morris遍历实现O(1)空间。核心还是“如何在不借助栈的情况下从一个节点走到它的后继”。我强烈建议把Morris前序遍历和Morris中序遍历都手写一遍然后回来看114题。你会发现114题就是“Morris遍历过程中顺手把left清掉”的变体。三套代码放在一起对照记忆会牢固得多。5.2 链表类题目的指针操作对照这道题的另一头通向经典链表题。展开后的二叉树本质上就是一条单链表而操作过程中大量出现“找尾节点”“重定向next”“头尾相接”这类模式。刷热榜时你会发现160题相交链表、206题反转链表、21题合并两个有序链表以及hot100里其他链表题都在锻炼同一种能力在任何有限的局部信息下安全地改变指针指向而不丢失数据。具体到114题这里有一个值得提炼的通用技巧当你在修改某个节点的指针之前先问自己一句——原来的引用还在哪里如果原来的位置被覆盖了有没有另一个位置已经保留了它养成这个习惯之后链表类题目的“指针丢失”问题就会少很多。比如206反转链表核心是next cur.next保存旧引用再改cur.next prev。114题里的predecessor.right cur.right本质上也是保存旧引用——只不过它把整棵右子树的引用“备份”到了左子树最右节点的right上。两种操作殊途同归。5.3 面试时的“由易到难”讲法如果你正在准备面试不妨把这道题设计成一个“层层深入”的展示题。我的建议讲法是第一步先讲清楚题意先序顺序、right串联、left置空。第二步给出递归解法说明它能AC但不满足O(1)空间。第三步引入前驱节点法重点讲“为什么找左子树最右节点”以及“为什么操作顺序不能反”。第四步用一个具体用例现场走一遍展示指针变化。这套讲法的好处是即使面试官没看过这道题也能顺着你的思路理解到位。而如果你一上来就甩出O(1)空间写法反而会因为缺少铺垫让面试官觉得你在背答案。6. 实测心得这道题刷几遍才算真正掌握我自己的经验是LeetCode的AC只是最低标准真正的标准是你能否在完全不看题解的情况下用三种不同思路各写一遍并且准确说出各自的时空复杂度。对114这道题我要求自己满足以下五条才算“过”先序遍历递归版能5分钟写对。后序拼接递归版能5分钟写对。前驱节点法能10分钟写对且不需要停顿思考操作顺序。能用手画出[1,2,5,3,4,null,6]每一步的指针变化。能说清楚为什么时间复杂度是O(n)均摊而不是O(n^2)。只有能做到这五条我才敢在面试中说“这道题我熟”。最后分享一个小技巧刷完114后顺手把predecessor的查找逻辑提取成一个独立函数比如find_rightmost(node)然后在Morris遍历里复用。你会发现很多二叉树的困难题比如二叉树最近公共祖先、BST迭代器都会用到类似的结构。把一个题吃透然后把提炼出的组件迁移到其他题里这才是刷hot100的终极目的。