CS-Notes 剑指 Offer 第 36 题：把二叉搜索树转换为排序的双向链表——原理剖析与完整实现

CS-Notes 剑指 Offer 第 36 题：把二叉搜索树转换为排序的双向链表——原理剖析与完整实现

【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes

本文基于 CS-Notes 仓库中的 36. 二叉搜索树与双向链表 一题展开，讲清"如何在不创建任何新节点的前提下，仅调整指针就地把一棵二叉搜索树（BST）转换为按值排序的双向循环/线性链表"的完整解题思路：从 BST 中序遍历有序这一核心性质出发，逐行拆解官方 Java 解法的三个关键状态变量，并配合仓库中的图示与相关笔记（BST 后序判断、第 K 个结点、Java 容器中的双向链表）完成一次系统性的复盘。读完本文，你应能独立完成该题手写实现、正确分析其时间/空间复杂度，并能在面试中解释每个指针修改的必要性。

一、题目描述

原题（见 36. 二叉搜索树与双向链表）：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

上图正是原题配图：左侧是节点值分别为 2（根）、1（左子）、3（右子）的二叉搜索树，右侧是转换结果——节点 1、2、3 按升序首尾相接，任意相邻节点之间既有正向指针又有反向指针。题目中"排序"指的是按节点值从小到大排列；"不能创建新节点"则意味着转换必须是原地（in-place）的，只能复用树中已有的节点及其left、right两个指针域。

这道题也是剑指 Offer 题解目录（见 剑指 Offer 题解 - 目录）中的第 36 题，是 BST 章节中综合性最强的一道：它同时考察 BST 的性质理解、中序遍历的变形运用、以及链表指针操作的严谨性。

二、解题思路：两个关键洞察

1. BST 的中序遍历天然是有序的

二叉搜索树满足"左子树所有节点值 < 根节点值 < 右子树所有节点值"的性质，因此对 BST 做中序遍历（先访问左子树，再访问根，最后访问右子树），得到的访问序列必然是一个严格递增的有序序列。

这一点可以对照仓库中的另一道题 33. 二叉搜索树的后序遍历序列 来理解：第 33 题判断一个数组是否为 BST 的后序序列，正是反复利用了"以最后一个元素为根，左段全小于根、右段全大于根"这个 BST 有序性特征。中序与后序同理，只是有序性在中序下直接体现为整条扫描序列有序，这正是本题的立身之本。

因此，题目要求的"排序的双向链表"不需要任何排序算法——遍历顺序即排序顺序，我们只需在中序访问每个节点的同时，把访问过的节点串成双向链表即可。

2. 复用left、right指针充当链表的prev、next

双向链表节点的左右指针（prev/next）与树节点的left/right在结构上完全同构：转换完成后，链表中"上一个节点"恰好放在原left指针位置，"下一个节点"恰好放在原right指针位置。所以：

• 每个节点被中序访问时，它的左子树已全部处理完，链表的"前驱"节点（记作pre）已经确定；
• 于是把node.left = pre、pre.right = node，就把pre与node这两个相邻节点的双向连接一次性建好；
• 全程没有任何new操作，节点数量、内存布局均不变，完全满足"不能创建任何新结点"的约束。

仓库中 Java 容器 一节系统介绍了双向链表的形态与应用（如LinkedList基于双向链表实现、LinkedHashMap用双向链表维护插入序/LRU 顺序），可以作为"双向链表为什么值得用这种结构"的背景知识。

3. 需要维护的三个状态

沿中序递归遍历时，需要三个成员变量记录全局进度：

为什么头节点必须单独记录？因为中序递归是从根节点开始的，第一次走到最左边的路径时才会遇到最小值节点，只有"第一个被中序访问到的节点"才是链表的head，这一点无法从根节点推导出来，只能靠head == null判断来捕获。

三、完整解法代码与逐行解析

下面是原笔记给出的完整 Java 解法（与 36. 二叉搜索树与双向链表 中的实现一致）：

private TreeNode pre = null; private TreeNode head = null; public TreeNode Convert(TreeNode root) { inOrder(root); return head; } private void inOrder(TreeNode node) { if (node == null) return; inOrder(node.left); node.left = pre; if (pre != null) pre.right = node; pre = node; if (head == null) head = node; inOrder(node.right); }

逐行拆解inOrder方法的核心五步（对应"访问当前节点"这一中序时机）：

1. if (node == null) return;：递归终止条件，空子树直接返回。
2. inOrder(node.left);：先递归处理左子树。递归返回时，左子树所有节点已经按中序顺序串入链表，且pre指向左子树中"最后被访问"的节点（即当前节点在整个中序序列中的直接前驱）。
3. node.left = pre;：把当前节点的left指针改指向前驱节点。这一步无条件执行——即使pre为null（当前节点是最小值节点，即链表头），把头的left置null也是正确的。
4. if (pre != null) pre.right = node;：反向补链。前驱节点的right必须指回当前节点，双向连接才算完整。注意此步有pre != null保护：链表头节点没有前驱，若不做判断会触发空指针异常。
5. pre = node;与if (head == null) head = node;：推进游标；同时利用"中序第一个访问的节点就是最小值节点"这一点，一次性捕获链表头。

最后inOrder(node.right);递归处理右子树，右子树节点会以node为前驱继续向后串接。

Convert方法本身只是入口：驱动中序遍历一次，然后返回捕获到的head。返回值是链表头而非任意节点，调用方可以只拿到头指针沿right单向遍历整个有序链表。

四、结合示例图推演执行过程

以仓库配图为例：BST 结构为 2 为根，左子 1、右子 3。按上述算法执行：

最终返回head（值为 1 的节点）。可以看到，每一步指针修改都发生在"左子树已完全处理"的时刻，前驱pre始终有效，这正是中序遍历相对前序/后序遍历的独特优势——当前节点被访问时，其左子树全部节点、以及它的前驱，都已被确定性地处理好。

顺带一提：转换完成后原树的父子关系完全消失（left/right已被复写），这是题目允许且预期的结果；如果需要还原，必须另存原始结构。

五、复杂度与边界情况

• 时间复杂度 O(n)：中序遍历恰好访问每个节点一次，每个节点的指针操作都是 O(1) 常数步。
• 空间复杂度 O(h)：递归调用栈深度等于树高 h。平衡 BST 为 O(log n)，退化为链时最坏 O(n)。不创建任何新节点，满足题目约束。
• 边界情况：
  • 空树（root == null）：inOrder立即返回，head保持null，返回null，行为正确；
  • 单节点树：node.left = null，head指向该节点，得到一个"双向链表"退化为单节点，正确；
  • 全部节点值不同是 BST 题面的隐含前提，若允许重复值，有序性依然成立，只是"严格递增"变为"非递减"，算法不受影响。

六、延伸与仓库内相关材料

• BST 性质类题目的横向对比：仓库中 33. 二叉搜索树的后序遍历序列 用递归分段验证 BST 有序性；54. 二叉查找树的第 K 个结点 则用中序计数找第 K 小值。第 36 题与第 54 题共享同一个技术内核——BST 中序 = 有序序列，前者是"把有序序列连成链表"，后者是"在有序序列上按下标取值"。
• 树的遍历框架：8. 二叉树的下一个结点 同样展示了"中序序列前后继"这一概念在不同场景下的指针操作，可与本题的pre游标思路互相印证。
• 双向链表背景知识：Java 容器 中关于LinkedList（双向链表实现）与LinkedHashMap（双向链表维护插入序/LRU 序）的说明，有助于理解为什么"有序的双向链表"是一个高频数据结构形态——本题的产物本质上就是一棵 BST 的"中序线性化"。

综上，本题的最优解就是一次中序遍历 + 三个状态变量：用 BST 的有序性免掉排序，用节点指针的同构性免掉新节点，把"树到链"的转换压缩为访问瞬间的常数次指针赋值。

【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes