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

本文基于 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. 需要维护的三个状态

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

变量	含义
pre	中序序列中上一个被访问的节点，初始为 null，每访问一个节点后更新为当前节点
head	双向链表的头节点，即中序序列中的第一个节点（BST 的最小值节点），只在第一次赋值
root（入参）	待转换树的根节点

为什么头节点必须单独记录？因为中序递归是从根节点开始的，第一次走到最左边的路径时才会遇到最小值节点，只有"第一个被中序访问到的节点"才是链表的 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。按上述算法执行：

步骤	访问节点	pre 处理	head 处理	链表状态（<-> 表示双向已连通）
1	1（最左）	1.left = null；pre 更新为 1	head 首次赋值 = 1	1（孤立）
2	2（回到根）	2.left = 1；1.right = 2	已有，不变	1 <-> 2
3	3（最右）	3.left = 2；2.right = 3	已有，不变	1 <-> 2 <-> 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 的有序性免掉排序，用节点指针的同构性免掉新节点，把"树到链"的转换压缩为访问瞬间的常数次指针赋值。