)
本题采用深度优先搜索迭代归并算法又称“递归中序周游法”解决二叉树节点的标准化顺序遍历问题。其核心本质是利用二叉树的递归拓扑结构遵循“左子树-根节点-右子树”的严格时序进行空间轨迹检索。当前提供的源码实现了在时间复杂度 O(N) 和额外空间复杂度 O(H)H 为树高条件下的全局最优深度检索最终走向是精准输出符合中序拓扑序列的节点数值集合。一、 问题本质与数据模型对于由TreeNode维系的非线性二叉树结构每个节点包含一个数值val以及分别指向left和right的两个后继引用。中序遍历Inorder Traversal的物理意义是完成非线性结构向线性结构的单调映射。其核心物理模型依赖于深度优先遍历DFS的递归回溯特性左边界探针探索控制流必须优先穷尽当前节点的所有左侧子孙节点。轴心状态消费在左子树完全归于“空null”的边界后方可处理当前根节点。右边界平移延伸根节点处理完毕后控制流平移至右子树重复上述拓扑检索过程。这种时序设计保障了在几何空间上所有节点按照“自左向右”的水平投影顺序被线性消费。二、 算法演进对比在解决二叉树中序遍历问题时基于隐式系统栈的递归深搜法在结构表达上具备高度的内聚性解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷显式栈迭代法O(N)O(H)显式创建外部 Stack 模拟系统调用栈通过手动控制指针压栈与弹栈实现回溯需要手动维护复杂的循环边界与指针状态代码抽象度低编写复杂度高莫里斯Morris遍历法O(N)O(1)利用叶子节点的空闲右指针指向前驱/后继节点构建临时线索二叉树会在遍历过程中动态修改并恢复树的拓扑结构在多线程并发读取场景下存在线程安全缺陷隐式栈递归法当前解法O(N)O(H)利用 JVM 原生的方法调用栈自动保存现场与回溯状态代码逻辑高度简化空间复杂度强依赖于树的高度在极端倾斜的退化链表树中会产生深度为 N 的栈帧存在栈溢出物理风险三、 核心分支控制逻辑与决策证明当前源码的控制流完全由dfs(root, ans)函数的隐式递归分叉网驱动其内部控制逻辑及决策证明如下1. 递归触底防御分支if (root null)执行return;终止当前递归分支并向上级回溯。物理证明当前指针为空意味着控制流到达了二叉树叶子节点的外部边界。结论当前子树的检索轨迹已穷尽控制流必须将控制权交还给上一层父节点防止引发空指针异常。2. 左向分叉深搜dfs(root.left, ans);执行将root.left作为新输入压入 JVM 递归栈。物理证明根据中序遍历的拓扑定义在任何节点被消费之前其左子树中的所有节点必须被优先处理。结论控制流持续向左下方深搜当前节点的上下文包括其自身的指针和当前执行位置被隐式保存在当前栈帧中。3. 数据流物理消费ans.add(root.val);执行将当前节点的数值添加至线性结果集合ans。物理证明此操作的触发时机位于dfs(root.left)执行完毕并弹栈之后。这意味着当前节点的所有左侧子孙节点已被完整遍历并写入集合。结论当前节点满足了中序时序的“轴心激活条件”执行线性数据捕获。4. 右向分叉转移dfs(root.right, ans);执行将root.right压入递归栈。物理证明在当前节点及左子树均处理完毕后右子树成为唯一未被探索的空间。结论控制流平移至右侧继续进行下一轮的“左-根-右”结构收敛。四、 算法执行状态机步进示例以输入二叉树root [1, null, 2, 3]即根节点 1无左子树右子树为 2节点 2 的左子树为 3为例递归调用栈及结果集状态演进如下表所示步骤当前激活节点递归阶段 / 执行动作JVM 隐式方法栈状态自栈顶向下结果集合 ans 状态拓扑物理剩余状态说明11进入dfs(1)触发dfs(1.left)dfs(null)-dfs(1)[]发现 1 的左子树为空准备回溯2nulldfs(null)触底直接returndfs(1)[]左子树处理完毕控制权交还给节点 131消费当前节点执行ans.add(1)dfs(1)[1]节点 1 写入准备向右探索dfs(1.right)42进入dfs(2)触发dfs(2.left)dfs(3)-dfs(2)-dfs(1)[1]控制流深入到节点 2 的左子树节点 353进入dfs(3)触发dfs(3.left)dfs(null)-dfs(3)-dfs(2)-dfs(1)[1]节点 3 尝试向左深搜触底6nulldfs(null)触底直接returndfs(3)-dfs(2)-dfs(1)[1]节点 3 左侧完毕控制权交还给节点 373消费当前节点执行ans.add(3)dfs(3)-dfs(2)-dfs(1)[1, 3]节点 3 写入触发dfs(3.right)空引用并退出dfs(3)82dfs(2.left)执行完毕消费节点 2dfs(2)-dfs(1)[1, 3, 2]节点 2 写入触发dfs(2.right)空引用并退出dfs(2)91dfs(1.right)执行完毕退出dfs(1)(空)[1, 3, 2]所有递归栈帧完全弹出全流程终结五、 源码实现/** * 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 ListInteger inorderTraversal(TreeNode root) { // 初始化线性结果集合用于存储中序序列数值 ListInteger ans new ArrayList(); // 启动深度优先搜索控制流 dfs(root, ans); // 返回完全收敛后的结果集合 return ans; } private void dfs(TreeNode root, ListInteger ans) { // 边界防护若当前控制指针触底 null终止该分支启动递归回溯 if (root null) { return; } // 步骤 1深度左向推进优先处理当前节点的所有左侧子孙拓扑 dfs(root.left, ans); // 步骤 2轴心状态激活将当前根节点的数值压入结果集合 ans.add(root.val); // 步骤 3平移右向推进处理当前节点的右侧子孙拓扑 dfs(root.right, ans); } }六、 复杂度分析1. 时间复杂度O(N)分析设二叉树中的节点总数为 N。算法的控制流通过递归分叉网对整棵树进行深搜。在整个运行期间每个节点在进入递归、左子树回溯、右子树平移时被精确访问常数次最多 3 次。同时对每个非空节点仅执行了一次ans.add(root.val)线性写入操作。结论总的方法压栈与数值存储操作次数与树的节点总数 N呈严格的线性正比关系。2. 空间复杂度O(H)分析该解法没有申请任何与输入规模成正比的显式外部动态数据结构ans属于题目要求返回的结果集不计入纯额外存储开销。然而递归的物理本质依赖于隐式方法调用栈JVM Stack。方法栈中同时存在的栈帧数量恒等于当前搜索路径的深度。对于高度为 H 的二叉树栈的最大深度为 H。若二叉树退化为单链表结构H 最大可达到 N在完全平衡二叉树状态下H 最小为 log N。结论额外内存开销完全取决于树的物理拓扑形态其辅助空间复杂度在最坏情况下退化为 O(N)平均状态下为 O(log N)整体表达为 O(H)。
)
