二叉搜索树转排序双向链表：中序遍历与指针重构详解

1. 先把这个题目彻底看透第一次看到把二叉搜索树转换成排序双向链表这句描述不少人的第一反应是题目里每个字都认识连在一起不知道从哪下手。这也正常这道题几乎是大厂面试里二叉树考题的分水岭——它同时考察对二叉搜索树性质的理解、对中序遍历的敏感度以及在不新建节点的情况下操作指针的能力。先说题目到底要求什么。输入是一棵普通的二叉搜索树每个节点有 left 和 right 两个指针要求把这棵树原地改造成一条有序的双向链表不能用任何额外的节点空间只能修改原有节点指针的指向。转换完成后链表的顺序必须和 BST 中序遍历的顺序一致链表中每个节点的 left 相当于双向链表的 pre 指针right 相当于 next 指针。有的版本还会额外要求首尾相连成环循环双向链表这个后面单独说。这个问题的经典程度不用我强调剑指Offer原题各大刷题平台也都收录了。适合的人群很明确准备校招或社招算法面试的同学、正在复习数据结构想加深理解的开发者以及很久没碰二叉树想找回手感的老程序员。难度定位是中等偏上但解法并不复杂只要思路通了代码量其实非常小。1.1 核心考点拆解到底在考什么面试官抛出这道题绝对不是只想听你背一段代码。他真正想看的是三件事。第一你是否理解 BST 的中序遍历结果就是有序序列。这是全题的钥匙一句话说得出来后面所有解法都是围绕它展开的。二叉搜索树满足左子树所有节点值 当前节点值 右子树所有节点值中序遍历按 左-根-右 的顺序访问输出天然有序。我们要的排序双向链表本质就是把中序遍历访问节点的顺序记录下来再用指针串起来。第二你是否敢动原有结构。题目明说不能创建新节点意味着你需要复用每个节点的 left 和 right 字段。很多新手被树这个概念框住潜意识里觉得 left/right 就是子节点指针不敢拿它们当双向链表的 pre/next 用。转换完成后这棵树也就不再是树了理解这一点代码就敢写了。第三边界处理能力。空树、单节点、只有左孩子或只有右孩子的斜树这些极端情况能不能一次写对往往决定面试结果。后面我会专门列一组测试用例建议大家拿它们逐一验证自己的写法。1.2 为什么说中序遍历是唯一正确的切入点题变成链表之后它的顺序是固定的就是中序序列。你不可能用前序或后序去排出一个有序链表因为 BST 只有中序遍历能保证升序。这也意味着无论用递归、迭代还是分治来实现遍历顺序一定是 左-当前-右 这个框架。想清楚这一层转换这个动作就简化成一件事在中序遍历的过程中把当前访问的节点与上一个访问的节点用双向指针连起来。上一个节点的 right 指向当前当前节点的 left 指向上一个。整个序列串完双向链表自然成型。2. 解法一递归中序遍历用一个全局指针串起所有节点2.1 核心思路最容易理解也最推荐面试优先写的方案就是中序遍历递归 一个记录上一个节点的指针。具体做法是维护两个成员变量head 记录链表头即中序遍历第一个节点pre 记录当前已处理部分的最后一个节点。递归进行中序遍历每访问到一个节点就把 pre.right 指向当前节点、当前节点.left 指向 pre然后更新 pre 为当前节点。遍历结束后返回 head。为什么需要 pre因为双向链表连接的是相邻两个节点而在递归过程中我们只能拿到当前节点上一个节点不会自动出现在参数里所以必须用一个外部变量记住它。2.2 Python 实现class TreeNode: def __init__(self, val): self.val val self.left None self.right None class Solution: def __init__(self): self.pre None self.head None def convert(self, root: TreeNode) - TreeNode: if not root: return None self.inorder(root) return self.head def inorder(self, cur: TreeNode) - None: if not cur: return # 左子树 self.inorder(cur.left) # 处理当前节点与 pre 建立双向连接 if self.pre: self.pre.right cur cur.left self.pre else: # pre 为空说明当前是最左节点也就是链表头 self.head cur self.pre cur # 右子树 self.inorder(cur.right)注意个别平台或面试场景要求不允许使用类成员变量。这种情况下可以用返回值 闭包数组或函数参数传引用替代。Python 里可以用一个长度为 1 的列表[None]存放 pre避免类成员变量带来的状态残留问题。2.3 用一棵示例树完整走一遍我拿下面这棵 BST 做演示4 / \ 2 6 / \ / \ 1 3 5 7中序遍历顺序是 1 2 3 4 5 6 7。递归过程先一路向左走到节点 1。此时 pre 为 None所以 head 1然后 pre 1。回溯到节点 2。pre 不为空执行 pre.right 2、2.left pre即 1 和 2 互相连接pre 2。访问节点 3和节点 2 互相连接pre 3。继续回溯到根节点 4和节点 3 互相连接pre 4。右子树同理5 连到 46 连到 57 连到 6。最终从左往右沿着 right 指针遍历1 - 2 - 3 - 4 - 5 - 6 - 7从右往左沿着 left 指针遍历7 - 6 - 5 - 4 - 3 - 2 - 1。双向链表完成。时间复杂度 O(n)每个节点访问一次空间复杂度 O(h)h 是树高因为递归栈占用。极端情况下树退化成链表h n递归深度就是 n这时候空间复杂度退化为 O(n)。这也是后面要讲迭代解法的一个原因。3. 解法二分治递归让每个子树自己返回头和尾3.1 思路差异如果说解法一是边遍历边串解法二就是先各自搞定再拼接。核心套路是写一个递归函数处理以 node 为根的子树返回两个值——这棵子树转换完成后的链表头 head 和链表尾 tail。处理过程分三步先递归转换左子树得到 leftHead 和 leftTail再递归转换右子树得到 rightHead 和 rightTail最后把当前节点接到左链表尾部、右链表头部接在根之后。这个思路的好处是递归逻辑非常对称面试时口头描述很清晰每棵子树负责把自己变成一个完整的双向链表段根节点负责把左右两段拼起来。3.2 Python 实现class Solution: def convert(self, root: TreeNode) - TreeNode: if not root: return None head, _ self.convert_subtree(root) return head def convert_subtree(self, node: TreeNode): # 返回 (链表头, 链表尾) if not node: return None, None left_head, left_tail self.convert_subtree(node.left) right_head, right_tail self.convert_subtree(node.right) # 左链表尾 - 当前节点 if left_tail: left_tail.right node node.left left_tail # 当前节点 - 右链表头 if right_head: node.right right_head right_head.left node head left_head if left_head else node tail right_tail if right_tail else node return head, tail3.3 两种递归解法的取舍对比维度解法一全局 pre解法二分治返回头尾代码量更短逻辑集中稍长但结构对称理解难度依赖对pre 变量的理解更接近分而治之直觉面试风险类成员变量易在多测试用例间残留状态无状态残留问题处理循环链表变体需要额外找头/尾串环拿到 tail 直接串环更方便我给的建议是面试优先写解法一因为它代码最少、最容易背、出错概率低但解法二也要能讲清楚尤其当面试官追问如果要求返回环形双向链表怎么办时解法二天然有尾指针三行就能改成环形版本。实战心得很多同学两个解法都背过但一写就错在head 是否为空或tail 是否为空这种分支上。我的经验是先画一棵三层满二叉树把左右子树的 head/tail 用记号标出来再对着图写 if 判断基本不会漏。4. 解法三迭代中序遍历用栈替代递归4.1 为什么要准备这个版本递归解法在绝大多数面试场景下已经够用但有两个场景会让你需要迭代版。第一个是树很高的情况。Python 默认递归深度约 1000 层如果面试官出的是类似节点数很大、近似链化的 BST递归直接触发 RecursionError。写迭代版至少能证明你考虑到了工程里的深度限制。第二个是加分项。当你用递归写完并讲完复杂度后主动补一句如果担心栈溢出我还可以用显式栈模拟中序遍历面试官通常会觉得你基本功扎实。4.2 迭代版实现class Solution: def convert(self, root: TreeNode) - TreeNode: if not root: return None stack [] cur root pre None head None while cur or stack: # 一路向左把路过的节点压栈 while cur: stack.append(cur) cur cur.left cur stack.pop() # 与 pre 建立双向连接 if pre: pre.right cur cur.left pre else: head cur pre cur # 转向右子树 cur cur.right return head这段代码的本质就是把递归中序遍历改成显式栈版本连接节点的动作和解法一完全一致只是 pre 从成员变量变成了局部变量。因为栈在函数内创建天然不担心多测试用例状态污染写在一个方法里就能直接跑。空间复杂度同样是 O(h)但这里的 h 是栈的最大深度且不受语言递归栈限制的影响可控性更好。5. 边界情况与验证方法5.1 必测的四种输入面试和实际刷题时不要只跑题目给出的正常用例。我每次写这种二叉树题都会固定测这四类输入空树root 为 None返回值应该是 None代码不能崩溃。单节点树只有一个根节点转换后链表头尾都是它自己left 和 right 都应为 None。只有左子树的斜树例如节点按 3-2-1 排列中序遍历是 1 2 3要确保 head 是最深的左孩子而不是根。只有右子树的斜树例如 1-2-3中序遍历也是 1 2 3要确保 head 是根节点。这四类用例几乎能覆盖 80% 的指针连接 bug。核心就一句话链表头一定是中序遍历第一个访问的节点而不是树的根节点。5.2 验证结果是否正确的技巧转换完以后怎么确认没写错最直接的办法是双向走一遍。先沿着 head 的 right 指针走到尾记录访问节点个数再从尾沿着 left 指针走回头记录节点个数。两次个数相等且都等于原树节点数同时遍历过程中每个节点的值严格递增就基本正确了。def verify(head: TreeNode, total: int) - bool: if not head: return total 0 # 正向遍历 cur head cnt 0 pre_val None while cur: if pre_val is not None and cur.val pre_val: return False pre_val cur.val cur cur.right cnt 1 # 反向遍历 cur head while cur and cur.right: cur cur.right cnt2 0 pre_val None while cur: if pre_val is not None and cur.val pre_val: return False pre_val cur.val cur cur.left cnt2 1 return cnt cnt2 total注意这个验证函数是本地调试用的面试时通常不用写完整但你要有意识在脑子里跑一遍双向遍历来检查自己的输出结构。5.3 临时输出检查法如果你用的是支持可视化调试的 IDE可以在每次连接后打印当前节点的连接关系。更轻量的办法是把链表 dump 成数组对比def dump(head: TreeNode): res [] cur head while cur: res.append(cur.val) cur cur.right return res原地改造类的题目dump 成数组和理论中序序列对比是最直观的验证方式没有之一。6. 高频变体转成循环双向链表6.1 题目怎么变有些公司会在这道题后面追加一句转换后首尾也要相连形成循环双向链表。这个要求在不少平台的题目里出现过把二叉树展平成循环链表。难度不高但对理解双向链表连接有更高要求。6.2 怎么改在非循环版本结束后我们已经有了链表头 head 和链表尾 tail解法一里需要额外遍历到尾部拿到 tail解法二直接返回了 tail。只需要两条连接if tail: tail.right head head.left tail注意一个坑如果你用解法一的递归pre 在遍历结束后正好指向链表尾所以你不需要再走一遍找 tail直接用 pre 当 tail 即可。这个细节很多人不知道白白多写了一个 while 循环。6.3 验证循环版本循环链表没法用 None 判断结尾改法是用一个计数变量走到 total 个节点就停止。也可以在转换前先数一下节点总数。我个人更推荐把总数当参数传进验证函数循环版本里正向走 total 次、反向走 total 次都能回到 head 就说明连接没断。7. 常见 bug 与排查实录7.1 head 被覆盖成 None新手最常见的错误是递归到第一个节点时先判断 pre 是否为空如果为空就设置 head但如果把这段写在更新 pre之后或者提前 returnhead 就可能一直是 None。排查思路很简单在设置 head 的那一行打点确认只执行一次。7.2 左指针没有被清零转换前每个节点的 left 指向左孩子转换后 left 是链表的前驱。如果某节点的 left 还指向原左孩子正向遍历可能看不出问题反向遍历会死循环。这也是为什么我建议一定要双向验证。7.3 类成员变量状态残留解法一如果用类成员 pre/head在同一个 Solution 对象上连续跑两个测试用例第二个用例读到的 pre 还是第一个用例的尾部节点直接导致结果错乱。解决办法有两个在 convert 方法开始时重置 pre 和 head或者改用局部变量 列表传递。多数刷题网站会新建对象但本地调试时容易踩这个坑。7.4 递归深度过深斜树导致递归深度等于节点数上面提过。遇到报 RecursionError要么转迭代要么在面试里明确说明生产环境我会用栈模拟。7.5 忘记处理空树这是最简单也最伤人的 bug。任何树类题第一行写if not root: return None都是好习惯检查一下没坏处。8. 面试现场怎么讲以及这道题还可以怎么扩展这道题面试现场的表达顺序我建议按这个节奏来先花 20 秒说清思路BST 中序遍历有序所以用中序遍历边遍历边连指针然后画一棵示例树口头演示两个节点怎么互连再写代码边写边强调 pre 和 head 的维护最后主动说复杂度。整个过程控制在三到五分钟。如果面试官追问重点往往在能不能不递归和能不能返回环形链表这两点上也就是上面解法三和变体部分。我个人在实际操作中的体会是二叉树相关的题最忌上来就写代码。先把中序序列 链表顺序这句话写在草稿纸上再开始动笔思路基本不会跑偏。这道题我前后给不下十个同学讲过卡住的几乎都不是递归不会写而是不敢把 left/right 当成链表的 pre/next 用。想通了这一点后面再遇到把一棵树改成某种线性结构的题都是一个套路。另外这题的思路可以迁移到不少相邻场景把二叉搜索树转成有序双向链表、把 BST 转成递增序列数组、先序遍历版本的展平二叉树为链表、甚至 Morris 遍历优化的空间压缩。练习时可以试着把解法一改成 C 或 Java 再写一遍感受指针和引用的差异对面试帮助很大。最后再分享一个小技巧本地练习时把树构建、转换、验证三条逻辑写在一个测试脚本里每次改完代码一键跑通比手动造数据高效得多。