《剑指Offer》第26题——二叉搜索树与双向链表，是我当年刷算法题时印象非常深刻的一道。第一次看到这个标题，脑子里冒出来的问题是：树结构用左右孩子指针组织数据，双向链表用前后节点指针组织数据，这俩平时看着八竿子打不着，怎么就画上等号了？真等我把题目彻底想明白才发现，关键不在“怎么转”，而在中序遍历——二叉搜索树的中序遍历结果天然有序，而双向链表恰恰是一个有序序列的线性载体。搞清楚这一层，解法基本上就浮出水面了。
这道题在不少公司的算法面试中都出现过，在经典刷题集里是第26题，在英文判题平台上对应的是链表版本。题目本身也很有“面试味”：要求不能创建任何新节点，只能调整树中节点的指针指向，最后返回一个排序的双向链表头节点。换句话说，考的不只是你知不知道中序遍历，还考你对指针操作、递归边界、引用传递的掌控。这篇文章我不打算只给一个答案，而是从原理、多种解法、边界情况到面试表达，完整拆一遍。
1. 题目到底在考什么：树与链表之间的一张“隐式契约”
很多刚接触这道题的人会把它归为“二叉树遍历”或“链表操作”，但我觉得它真正的主题是结构转换。二叉搜索树（BST）的核心性质只有一条：左子树所有节点的值都小于根节点，右子树所有节点的值都大于根节点。正因为这个性质，对BST做一次中序遍历，得到的就是一个从小到大排列的序列。
双向链表的核心能力是：从头到尾可以顺序访问，从尾到头也能顺序访问，每个节点持有前驱和后继两个指针。你看，BST的节点也有左右两个指针。所以题目本质上是在问你：能不能在不新建节点、不破坏原结构信息的前提下，把“树的左右关系”重新解释成“链表的前后关系”，并保持顺序约束？这就是我所说的“隐式契约”——树的左指针变成链表的前驱指针，树的右指针变成链表的后继指针。
既然是中序遍历给出有序序列，那转换策略就清楚了：按中序遍历的顺序访问每个节点，把当前访问到的节点和“上一个访问到的节点”用指针连起来，访问完整个树，所有节点就自然串成了一条有序链表。这里有一个很关键的前提：题目要求原地调整，不能创建新节点。有人可能会想“那我先中序遍历把所有节点存进数组，再改指针”，这种方案虽然结果对，但在面试里会立刻被追问“存数组占用了额外O(n)空间，能不能不用？”所以真正合格的做法，是在遍历的同时完成连接。
还有一点要留意：这里说的“双向链表”，在不同题目版本里要求不完全一样。经典刷题集的原始版本只要求排序的双向链表，头节点的前驱和尾节点的后继留空就行；但英文判题平台上要求返回的链表是循环双向链表，也就是头节点和尾节点也要互相连接。面试答题前最好先和面试官确认清楚，别写了半天最后在“是否成环”上扣分。下面所有代码我先按循环链表来写，最后会单独告诉你改成非循环版本要动哪一行。
2. 最主流的解法：中序遍历过程中用pre指针“穿针引线”
思路既然定下来了，实现就顺理成章。我们维护一个pre变量，表示“当前节点在中序遍历顺序下的前一个节点”。每访问到一个新节点cur，就做两件事：把pre的右指针指向cur，把cur的左指针指回pre。然后更新pre = cur。当整棵树遍历完，pre就是中序遍历的最后一个节点，也就是链表的尾节点。再用一个head变量记住第一个被访问的节点作为头节点，最后把head.left = pre、pre.right = head，循环链表就闭合了。
2.1 递归版代码与执行过程拆解
先写最直观的递归版本，Python代码如下：
class Node: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def treeToDoublyList(self, root: 'Node') -> 'Node': if not root: return None head = None pre = None def dfs(cur): nonlocal head, pre if not cur: return # 先处理左子树，保证访问顺序是“左 -> 根 -> 右” dfs(cur.left) # 第一个被访问的节点就是链表的头 if pre: pre.right = cur cur.left = pre else: head = cur # 更新pre，继续向右子树递归 pre = cur dfs(cur.right) dfs(root) # 首尾相连，形成循环双向链表 head.left = pre pre.right = head return head你可能会好奇，为啥要先递归左子树，而不是先处理根节点？因为我们要的是中序序列。假设树是[4, 2, 5, 1, 3]，用中序访问顺序就是 1 -> 2 -> 3 -> 4 -> 5。第一个被访问的节点一定来自最左侧，也就是整棵树的最小值，它就是链表的head。这个顺序一旦错位，链表就不有序了。
递归函数里最微妙的点是pre的传递方式。在Python里，如果你把pre作为普通参数传给dfs，在递归回退时它不会保留修改结果——因为整数和None这类不可变对象是值传递。所以我用nonlocal pre让dfs闭包共享外层变量，这样在任意一层递归里修改pre，其他层都能感知到。Java里没有nonlocal，通常做法是把pre定义成类的成员变量，或者用一个长度为1的数组当作“容器”传进去。这一点很多人面试时会写错，后面我会专门讲。
2.2 为什么pre必须跨递归传递：一个容易出错的细节
我先说说直接把pre当函数参数传会发生什么。伪代码如下：
def dfs(cur, pre): if not cur: return pre dfs(cur.left, pre) # 这里传入的pre还是上一次的值 ...问题在于：递归进入左子树时，pre在左子树内部确实被更新了，但更新发生在“那一层递归自己的局部变量”里；回到当前层时，外层的pre并没有拿到更新后的值。结果就是，当你在当前节点做连接时，连到的还是旧的、甚至为空的pre，节点之间的指针就会断开。这就是为什么在递归回溯模型里，必须用全局变量、nonlocal、返回值、或者持有引用类型的容器。理解了这一点，面试时就不容易被细节卡住。
如果不想用nonlocal，也可以让递归函数返回“当前子树处理完后的最后一个节点”，这样本质上是用返回值把pre带出来。比如：
def dfs(cur, pre): if not cur: return pre pre = dfs(cur.left, pre) if pre: pre.right = cur cur.left = pre else: head = cur pre = cur return dfs(cur.right, pre)两种写法本质相同，但第一种用闭包变量往往更好读，也更贴近“维护一个全局游标”的心智模型。你可以在面试时先写nonlocal版本，简单直接，再提一句“如果用Java可以把pre提为成员变量”，展示你考虑过不同语言的差异。
2.3 循环与非循环版本就差两行
如果面试官要的是经典刷题集里的非循环链表，只需要把最后两行删掉，返回head即可：
dfs(root) return head # 不连接 head.left 和 pre.right如果是循环链表，最后两行head.left = pre; pre.right = head必不可少。我做面试模拟的时候发现，很多候选人在解释“为什么要让head.left指向pre”时会卡壳。原因是：中序遍历结束后，pre是尾节点，它的right指针默认还指向某个子树节点或者为空，如果不显式改成head，整个链表就会在尾部断开或形成错误连接；同理，head.left如果不指向pre，你就无法从头部向前遍历回尾部。这一步的意义就是“把线性链表两端接起来”，是循环版本的收尾动作。
3. 另一种思路：左右子树分治回归再拼接
递归配pre指针是最常用的解法，但面试中如果你只会这一种，面试官很可能会追问“能不能换一种思路？”这时候分治法就派上用场了。它的核心想法是：把整棵树拆成左子树、根节点、右子树三部分，先把左子树转换成一条双向链表，再把右子树转换成一条双向链表，最后用根节点作为桥梁，把三条“链”拼成完整的一条。听起来简单，但实现时涉及的返回值设计和边界判断比pre指针法更烧脑。
3.1 分治法的核心：递归子任务的返回值设计
分治法的难点在于：递归函数到底该返回什么？如果只返回链表的头节点，拼接时你需要走到左链表的尾部，这需要额外O(n)时间。所以更聪明的做法是同时返回头节点和尾节点。在Python里可以返回元组，在Java里可以定义一个小结果类，或者用两个全局变量接住返回值。
def dfs(root): if not root: return None, None l_head, l_tail = dfs(root.left) r_head, r_tail = dfs(root.right) # 用root连接左链表和右链表 if l_tail: l_tail.right = root root.left = l_tail else: l_head = root if r_head: root.right = r_head r_head.left = root else: r_tail = root return l_head, r_tail这段代码的逻辑可以一句话概括：左子树的尾节点接root，root接右子树的头节点。左子树为空时，root自己就是整条链表的头；右子树为空时，root自己就是整条链表的尾。递归回到最上层时，返回的(l_head, r_tail)就是整棵树转换后的链表首尾。
3.2 拼接时四种边界情况全梳理
递归过程本身不长，真正容易出错的是“左子树/右子树是否为空”这四种组合。我建议你用一个简单例子手动推一遍：根节点是5，左子树只有一个节点2，右子树为空。此时l_head=2, l_tail=2, r_head=None, r_tail=None。进入拼接逻辑：l_tail非空，所以2.right = 5, 5.left = 2；r_head为空，所以r_tail = root = 5。最后返回(2, 5)。你看，这个结果恰好是一条从2到5的双向链表。
再看一个更复杂的情况：左子树为空，右子树只有一个节点7。此时l_head=None, l_tail=None, r_head=7, r_tail=7。拼接时，l_tail为空，所以l_head = root；r_head非空，所以root.right = 7, 7.left = root；返回(root, r_tail)。最终链表就是root -> 7。四种情况分别是：左右都非空、左空右非空、左非右空、左右都空。左右都空时，函数返回(root, root)，单个节点自成一条链表。我建议你在每道类似的“树转链表”题目里都刻意把递归出口和这四种情况画一遍，比死记代码有用得多。
3.3 递归法与分治法的取舍
从代码量看，pre指针法更短；但从“思路可解释性”看，分治法更接近“把大问题拆成独立子问题再合并”的通用方法论。面试时我一般先讲pre指针法为主解，因为它直接把“中序遍历+指针连接”这条主线讲清楚了；如果面试官追问“还有没有别的方法”，再讲分治法，同时强调“每次递归返回头尾两个节点，正是为了让上层拼接不再额外遍历链表”。两种方法的时间复杂度都是O(n)，空间复杂度都取决于递归深度，也就是树的深度O(logn)到O(n)之间。
有个细节很多人会忽略：分治法的拼接顺序其实也是一种“隐式的中序遍历”——先处理左子树，再处理根，再处理右子树。所以它和pre指针法在本质上是一家人，只是把“维护全局pre”变成了“由下层递归向上层返回局部链表的头尾”。理解了这个等价关系，面试时不管面试官怎么变着法问，你都能把两套讲法统一起来。
4. 迭代与Morris：不靠递归也能完成的进阶方案
递归虽然好写，但有一个天然短板：栈深度。如果树退化成长链，递归深度可能达到n，某些环境下会造成栈溢出。这时候用迭代版中序遍历就能避免这个问题。迭代版的切入点是“用显式栈模拟递归过程”，理解起来不算难，而且几乎可以把递归版的pre指针逻辑原封不动搬过来。
4.1 用栈模拟中序遍历实现转换
def treeToDoublyList(root): if not root: return None stack = [] cur = root pre = None head = None while stack or cur: # 一直往左走，把所有左孩子压栈 while cur: stack.append(cur) cur = cur.left # 弹出栈顶，等价于递归中的“访问当前节点” cur = stack.pop() # 连接操作与递归版完全一致 if pre: pre.right = cur cur.left = pre else: head = cur pre = cur # 转到右子树，继续循环 cur = cur.right head.left = pre pre.right = head return head这段代码里最容易被问到的点是：为什么内层while把左孩子全部压栈后，弹出的是中序第一个节点？因为栈是后进先出，最底层的左孩子会最后被压入、最先被弹出，这正好符合中序遍历“先左再根”的顺序。每次弹出节点后，再看它的右孩子，把右孩子的整条左链再压入栈，整个遍历过程就完整了。
迭代版的优势不只是避免递归栈溢出，它还把“当前节点”和“前驱节点”的关系变得更透明——你在循环体内可以清楚地看到每次连接发生时，pre和cur分别是谁。面试时如果候选人能熟练写出迭代版，通常会给面试官留下“基础扎实”的好印象，因为这说明你不是只背了递归模板。
4.2 Morris遍历：把空间复杂度压到O(1)
如果说迭代栈是“把递归栈搬到了堆上”，那Morris遍历就是“彻底不用额外栈”。它的原理是利用树中空闲的右指针来暂存回退信息：当某个节点没有右子树时，暂时让它的右指针指向中序遍历的下一个节点，这样遍历完左子树后，可以通过这个“临时线索”直接跳回祖先节点。
用Morris遍历实现本题的代码如下：
def treeToDoublyList(root): if not root: return None head = None pre = None cur = root while cur: if cur.left: # 找到左子树的最右节点（中序predecessor） predecessor = cur.left while predecessor.right and predecessor.right != cur: predecessor = predecessor.right if predecessor.right is None: # 建立临时线索，然后进入左子树 predecessor.right = cur cur = cur.left continue else: # 说明左子树已经处理完，撤销线索 predecessor.right = None # 访问当前节点 if pre is None: head = cur else: pre.right = cur cur.left = pre pre = cur # 进入右子树 cur = cur.right head.left = pre pre.right = head return head这段代码比前两版难懂不少，核心在于“当走到某个节点的左子树为空或左子树已处理完时，这个节点就是中序遍历的下一个待访问节点”。整个过程时间仍是O(n)，但空间只有O(1)。老实说，面试中能写出来的人不多，对我来说它是“加分项”而不是“必须项”——除了个别极其看重底层原理的面试官，大多数场景下你提一嘴“我知道可以用Morris把空间降到O(1)”就够了，现场手写Morris很容易在细节上卡壳。
4.3 三种方案复杂度一览
我把三种解法放在一起对比，方便你根据面试氛围选择讲解策略：
| 方案 | 时间复杂度 | 额外空间复杂度 | 优点 | 适用场景 |
|---|---|---|---|---|
| 递归+pre指针 | O(n) | O(树高)，最坏O(n) | 代码最短，思路直观 | 优先讲解，适合大多数面试 |
| 迭代栈+pre指针 | O(n) | O(树高)，最坏O(n) | 避免递归栈溢出，顺序清晰 | 被追问“递归有风险怎么办”时 |
| Morris遍历 | O(n) | O(1) | 空间最优，原理巧妙 | 进阶加分，或数组要求的O(1)空间题 |
5. 高频误区与面试实战：从“会写”到“拿分”
我在帮同学模拟面试的过程中，发现这道题非常容易暴露两类问题：一类是对指针连接顺序不敏感，另一类是写着写着把自己绕进递归。下面这几个坑，几乎每次面试都会有人踩，提前排一遍雷很有价值。
5.1 我见过最多的三类错误
第一个错误是搞反连接方向。双向链表要求“前驱的右指针指向后继，后继的左指针指向前驱”，有人会写成cur.right = pre，直接把当前的右指针指向上一个节点，这样链表就倒序了。正确的连接顺序永远是pre.right = cur和cur.left = pre，顺序不能换。第二个错误是pre没有正确传递。像Python里把pre当普通参数传给递归，Java里new了局部变量却不知道在递归中更新，都会导致链表只连上一两个节点。这一点在2.2节已经展开，这里是再次提醒：凡是递归中需要“跨层共享”的变量，要么提升作用域，要么显式返回。
第三个错误是忘了处理空树和单节点树。空树直接返回None，这个问题大多数人不会错；但单节点树很容易错。单节点树没有左子树也没有右子树，递归版运行时pre始终为None，head设成root，最后如果写成循环版，head.left = pre其实就是root.left = root，这没问题；但如果你实现非循环版却没调整，返回的head就有问题了。建议拿到题目后先手动跑两个用例：根节点本身，以及“根节点带一个左孩子”的最小树，能快速验证边界逻辑对不对。
5.2 如何用“先提出暴力方案”引导面试官
面试中很多候选人对“第一时间写出最优解”有执念，其实这反而容易被卡住。我的建议是先说一句：最简单的方式是先用中序遍历把所有节点存到数组里，再修改节点指针连成链表。这个方案空间O(n)，不符合题目“不创建新节点”的隐含约束，但可以作为讨论起点。你把暴力方案摆出来，面试官大概率会问“能不能不要用额外空间”，这时候你再推出pre指针法，讲解过程自然流畅。这不是绕弯子，而是展示你“能从朴素想法出发逐步优化”的思考能力，面试官也更愿意顺着你的思路做引导。
等到代码写完了，还有一步容易被忽略：主动解释为什么返回的是head而不是root。因为转换后原来的根节点不一定是链表的头节点——比如根节点还有左子树时，链表的头是最左节点。面试官看到你返回head会默认你理解这一点，如果你在口述中主动点明，会更加分。
5.3 相似题目的区分：别和“二叉树展开为链表”混在一起
很多刷题网站上还有一道经典题叫“二叉树展开为链表”，要求把二叉树按前序顺序展开成一个右指针相连的链表。那题和这道题至少有两点不同：第一，那题要求保持树形结构，节点的左指针全部置空，只保留右子树链；第二，那题用的是先序遍历而不是中序遍历。如果把二者的遍历顺序搞混，代码会满盘皆输。更稳妥的做法是：看到“二叉搜索树 + 有序 + 双向链表”这几个字眼，第一反应就是中序遍历；看到“展开成右子树形状”这种描述，第一反应才是前序。类似的还有“二叉搜索树转为累加树”，那道题要反向中序遍历，用一个pre记录累加值，思路和本题同源，只是方向相反。
6. 一点刷题心得：这道题背后的通用方法论
刷完这道题再回头看，你会发现它其实代表了算法面试里一个很重要的门类：树结构和线性结构之间的转换。这一类题的通用方法论可以提炼成三板斧：第一，想清楚目标线性结构的有序性由哪种遍历顺序保证；第二，设计好递归或迭代过程中“上一个节点”的传递方式；第三，明确最终返回哪个端点、是否需要首尾相连。把这三板斧刻在脑子里，不只是这道题，遇到“BST转累加树”“BST转双向链表”“二叉树展开为链表”都能快速找到切入点。
代码风格上，递归版虽然只有十几行，但边界条件一个都不能少。我自己的习惯是：写完后立刻测试三个用例——空树、单节点、以及一个三层的满二叉树。用三层满二叉树手动走一遍，基本能覆盖pre初始化、head赋值、尾节点连接的全部逻辑。如果你在刷题时能坚持对每道树结构题目都做这种“手动trace”，一个月后写递归的底气会明显不一样。
最后分享一个小技巧：面试时写完递归版，可以主动补一句“如果树退化成链，递归栈深度可能到n，想更稳可以用迭代栈版本，或者Morris遍历把空间压到O(1)”。哪怕现场不写完整代码，这句话也会让面试官觉得你对复杂度细节有足够敏感度。这道题真正的价值不在于背下答案，而在于让你掌握“遍历顺序决定结构形态”的思考方式——后续再遇到任何树和链表之间的转换，你都会下意识地先问自己一句：中序？先序？还是后序？
