)
本题采用逆后序遍历递归算法又称“反向后序链表重构法”解决二叉树原地展开为单链表的问题。其核心本质是通过“右-左-根”的逆向遍历顺序在不破坏尚未访问节点拓扑结构的前提下自底向上将节点逆序装配为单链表。当前提供的源码实现了在时间复杂度 O(n) 和额外空间复杂度 O(h)其中 h 为树的高度条件下的全局最优原地拉平最终走向是使二叉树的右子树完全等价于其先序遍历序列。一、 问题本质与数据模型对于给定的二叉树题目要求将其按照先序遍历根-左-右的顺序原地展开为单链表。在这个过程中面临一个核心的物理冲突如果按照常规先序遍历自顶向下直接修改当前节点的右指针将其指向左子树那么当前节点原本的右子树根节点指针将会被覆盖而物理丢失导致后续遍历无法推进。为了破除这种正向修改导致指针丢失的物理困局算法引入了“逆向链表重构模型”。由于先序遍历的终点是整棵树最右下角的节点算法选择反其道而行之采用“右子树 - 左子树 - 根节点”的逆后序遍历路径。在这种拓扑步进中最先被完整处理的是先序遍历的末尾节点。通过维护一个全局指针 head 指向已经构建好的链表头部每次回到当前节点时直接将其左指针置空右指针指向 head并将 head 更新为当前节点。这种自底向上、自右向左的逆序装配完美避开了指针覆盖问题实现了原位拉平。二、 算法演进对比在将二叉树原位拉平为先序单链表的场景中逆后序遍历法在空间利用与逻辑简洁度上表现优异解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷先序遍历加外部存储O(n)O(n)利用先序遍历将节点依序存入列表再遍历列表重构指针引入了与节点总数成正比的外部内存空间非原地修改逆后序递归法当前解法O(n)O(h)采用右-左-根逆序遍历利用全局 head 指针逆向串联链表强依赖递归调用栈在极度倾斜的树拓扑下空间退化为 O(n)寻找前驱节点法Morris 变体O(n)O(1)将左子树的最右节点先序前驱的右指针指向当前节点的右子树再将左子树移到右边改变了树的临时拓扑结构代码循环跳转控制较为繁琐三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于函数递归调用栈及全局变量 head 的状态更新其内部决策分支证明如下1. 基准退出分支if (root null)执行直接返回。物理意义触及虚拟空边界不做任何指针修改与变量更新直接退出当前层级的调用。2. 右子树先行压栈flatten(root.right);执行优先递归处理右子树。数学证明在先序遍历根-左-右中右子树是最后被访问的。在逆向重构中最后访问的必须最先处理。通过优先处理右子树使得右子树的所有节点率先被连接到链表的尾部即 head 的深层后继。3. 左子树次之压栈flatten(root.left);执行随后递归处理左子树。数学证明左子树在先序遍历中介于根和右子树之间。当右子树全部拉平并形成以当前 head 为首的链表后处理左子树会把左子树的节点逆序插入到右子树节点的前面动态维持了先序遍历的相对顺序。4. 指针重组与状态更新root.left null; root.right head; head root;执行断开左指针右指针指向 head更新 head。数学证明此时左、右子树已经完全被拉平并由 head 指向其链表首节点。按照先序遍历当前根节点 root 应该作为左子树首节点的前驱。因此令 root.right head 成功将当前节点接入链表头部再令 root.left null 满足题目对单链表物理结构的约束最后执行 head root 为上一层父节点的接入做好基建准备。四、 算法执行状态机步进示例以输入二叉树 root [1, 2, 5, 3, 4, null, 6] 为例规模 n 6演示全局变量 head 与递归树节点的步进状态转换后序遍历触发顺序为 6 - 5 - 4 - 3 - 2 - 1步骤当前访问节点值阶段判定条件与指针操作执行后的 head 指向空间调用栈物理状态说明初始1启动逆后序一路向右压栈至节点 6null栈深: [1, 5, 6]16左右均为空执行 6.right null, 6.left null6弹出 6返回至 525左为空右已处理。执行 5.right 6, 5.left null5 (链表: 5-6)弹出 5返回至 131右子树处理完毕转向左子树 2一路向右压栈5 (链表: 5-6)栈深: [1, 2, 4]44左右均为空执行 4.right 5, 4.left null4 (链表: 4-5-6)弹出 4返回至 252右子树 4 已处理转向左子树 34 (链表: 4-5-6)栈深: [1, 2, 3]63左右均为空执行 3.right 4, 3.left null3 (链表: 3-4-5-6)弹出 3返回至 272左右均处理完执行 2.right 3, 2.left null2 (链表: 2-3-4-5-6)弹出 2返回至 181左右子树全部拉平执行 1.right 2, 1.left null1 (链表: 1-2-3-4-5-6)弹出 1流程结束五、 源码实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public void flatten(TreeNode root) { // 基准收敛条件若当前节点为空直接返回退出当前层级调用 if (root null) { return; } // 逆后序步骤 1优先递归拉平右子树使其先进入单链表尾端 flatten(root.right); // 逆后序步骤 2随后递归拉平左子树使其接入右子树与根节点之间 flatten(root.left); // 逆后序步骤 3物理结构重组断开当前节点的左指针置为 null root.left null; // 逆后序步骤 4将当前节点的右指针指向已经构建好的单链表首节点head root.right head; // 逆后序步骤 5更新全局 head 指针使其指向当前节点供上一层父节点连接使用 head root; } // 全局变量用于暂存已构建链表的头部节点状态 private TreeNode head; }六、 复杂度分析1. 时间复杂度O(n)分析算法采用改进型的深度优先搜索DFS对二叉树中的每个节点进行且仅进行一次访问。在每个节点内部执行的指针断开、指针重连及全局变量赋值均属于标准的常数阶操作 O(1)。若树中包含 n 个节点总的操作步数与节点总量 n 呈严格的线性正比关系。结论时间复杂度为 O(n)原地拉平效率达到理论最值。2. 空间复杂度O(h)分析算法运行期间的额外空间完全由递归方法调用栈的物理深度决定。该深度取决于二叉树的高度 h。在最好情况下完全平衡二叉树树高为 log n 级别空间复杂度为 O(log n)在最坏情况下二叉树退化为单链表拓扑结构系统调用栈将同时存在 n 个方法帧空间复杂度退化为 O(n)。结论空间复杂度表示为 O(h)没有申请任何与输入规模相关的外部独立容器。
