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. 需要维护的三个状态沿中序递归遍历时需要三个成员变量记录全局进度变量含义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方法的核心五步对应访问当前节点这一中序时机if (node null) return;递归终止条件空子树直接返回。inOrder(node.left);先递归处理左子树。递归返回时左子树所有节点已经按中序顺序串入链表且pre指向左子树中最后被访问的节点即当前节点在整个中序序列中的直接前驱。node.left pre;把当前节点的left指针改指向前驱节点。这一步无条件执行——即使pre为null当前节点是最小值节点即链表头把头的left置null也是正确的。if (pre ! null) pre.right node;反向补链。前驱节点的right必须指回当前节点双向连接才算完整。注意此步有pre ! null保护链表头节点没有前驱若不做判断会触发空指针异常。pre node;与if (head null) head node;推进游标同时利用中序第一个访问的节点就是最小值节点这一点一次性捕获链表头。最后inOrder(node.right);递归处理右子树右子树节点会以node为前驱继续向后串接。Convert方法本身只是入口驱动中序遍历一次然后返回捕获到的head。返回值是链表头而非任意节点调用方可以只拿到头指针沿right单向遍历整个有序链表。四、结合示例图推演执行过程以仓库配图为例BST 结构为 2 为根左子 1、右子 3。按上述算法执行步骤访问节点pre处理head处理链表状态- 表示双向已连通11最左1.left nullpre更新为 1head首次赋值 11孤立22回到根2.left 11.right 2已有不变1 - 233最右3.left 22.right 3已有不变1 - 2 - 3最终返回head值为 1 的节点。可以看到每一步指针修改都发生在左子树已完全处理的时刻前驱pre始终有效这正是中序遍历相对前序/后序遍历的独特优势——当前节点被访问时其左子树全部节点、以及它的前驱都已被确定性地处理好。顺带一提转换完成后原树的父子关系完全消失left/right已被复写这是题目允许且预期的结果如果需要还原必须另存原始结构。五、复杂度与边界情况时间复杂度 O(n)中序遍历恰好访问每个节点一次每个节点的指针操作都是 O(1) 常数步。空间复杂度 O(h)递归调用栈深度等于树高 h。平衡 BST 为 O(log n)退化为链时最坏 O(n)。不创建任何新节点满足题目约束。边界情况空树root nullinOrder立即返回head保持null返回null行为正确单节点树node.left nullhead指向该节点得到一个双向链表退化为单节点正确全部节点值不同是 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考