《剑指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, leftNone, rightNone): 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这段代码的逻辑可以一句话概括左子树的尾节点接rootroot接右子树的头节点。左子树为空时root自己就是整条链表的头右子树为空时root自己就是整条链表的尾。递归回到最上层时返回的(l_head, r_tail)就是整棵树转换后的链表首尾。3.2 拼接时四种边界情况全梳理递归过程本身不长真正容易出错的是“左子树/右子树是否为空”这四种组合。我建议你用一个简单例子手动推一遍根节点是5左子树只有一个节点2右子树为空。此时l_head2, l_tail2, r_headNone, r_tailNone。进入拼接逻辑l_tail非空所以2.right 5, 5.left 2r_head为空所以r_tail root 5。最后返回(2, 5)。你看这个结果恰好是一条从2到5的双向链表。再看一个更复杂的情况左子树为空右子树只有一个节点7。此时l_headNone, l_tailNone, r_head7, r_tail7。拼接时l_tail为空所以l_head rootr_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始终为Nonehead设成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)”。哪怕现场不写完整代码这句话也会让面试官觉得你对复杂度细节有足够敏感度。这道题真正的价值不在于背下答案而在于让你掌握“遍历顺序决定结构形态”的思考方式——后续再遇到任何树和链表之间的转换你都会下意识地先问自己一句中序先序还是后序
