hot100 翻转二叉树(226)

本题采用自顶向下深度优先搜索算法又称“二叉树镜像翻转算法”解决二叉树的左右子树对调问题。其核心本质是将全局的“镜像对称”问题拆解为以任意节点为中心的基础指针交换利用递归纵向推进的特性在自顶向下的深度遍历过程中完成每一个节点左右物理指针的解耦与重组。当前提供的源码实现了在时间复杂度O(n)和额外空间复杂度O(height)条件下的全局最优树拓扑结构逆转。一、 问题本质与数据模型对于一个给定的二叉树题目要求的翻转是指将整棵树沿其中轴线进行完全的镜像对称变换。二叉树本身具有天然的递归分裂属性任何一棵树的翻转都可以映射为根节点的左右指针互换以及对其所有子代节点的递归互换。因此求解整棵树的翻转可以完全等价地转化为一个自顶向下的递推模型任何一个节点处的物理翻转 交换(当前节点的左指针, 当前节点的右指针) 递归翻转新的左子树 递归翻转新的右子树为了破除递归的无限下探算法引入了“空节点基准退出模型”。当程序深度探测至叶子节点的两侧空指针null时该位置不包含任何子节点表现出基础的边界属性命中空节点直接截断并原路返回。物理节点触发立即执行局部指针的三点交换借由临时变量完成并向子代继续派发任务。这种自顶向下的指针吞吐机制赋予了递归栈类似于“流水线染色”的物理特性确保在遍历完所有有效节点后全树的拓扑形态实现完美的镜像对调。二、 算法演进对比在解决二叉树翻转的问题时前序递归法在代码优雅度与空间效率上达到了经典平衡解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷层序遍历法BFS 迭代O(n)O(n)利用辅助队列进行按层扫描逐个弹出节点并直接交换其左右子节点需要显式借助队列存储当前层的所有节点在完全二叉树下其最底层宽度可达 n/2内存开销较大中序遍历递归法O(n)O(height)先递归翻转左子树再交换当前节点左右子树最后递归翻转新的右子树由于中序遍历改变了结构最后一步需要重复递归原左子树即新的右子树逻辑极易混淆前序递归法当前解法O(n)O(height)采用自顶向下策略先交换当前节点的左右子树指针再直接向两侧子树派发递归极度倾斜的树如链表状二叉树会导致递归栈深度退化为 O(n)三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于函数入口的边界防护以及自顶向下的指针改写其内部决策分支证明如下1. 基准出口分支if (root null)执行直接执行return;。物理意义当前坐标已越过叶子节点到达不存在的空子树检索流程在该分支触底并启动安全回溯防止引发空指针异常NullPointerException。2. 空间拓扑交换TreeNode temp root.left; root.left root.right; root.right temp;执行借助中介变量temp强制切断当前根节点与其原有左右子节点的物理连接并进行对调绑定。数学证明镜像翻转的本质是相对位置的置换。无论当前节点的左右子树内部结构多么复杂只要在当前层级将其左、右大骨架指针直接对调就已经完成了当前层级的绝对镜像。3. 递归下推分支dfs(root.left);与dfs(root.right);执行在当前节点指针对调完成后分别向新绑定的左、右子节点派发相同的翻转任务。物理意义当前层级交换完毕后子树内部的深层节点依然保持原有相对顺序。因此指针必须继续向下步进直到每一个子代节点的左右指针均被处理完毕实现全树的线性收敛。四、 算法执行状态机步进示例以输入二叉树root [2, 1, 3]规模 3 个有效节点为例调用栈的状态机演进及指针重组过程如下表所示步骤当前处理节点触发的分支动作当前节点左右子节点状态执行的核心交换决策局部拓扑变更状态说明初始节点 2 (根)进入dfs(2)左1, 右3temp暂存1root.left设为3root.right设为1节点 2 的左右子树对调完毕形态变为[2, 3, 1]1节点 3进入dfs(root.left)左null, 右nulltemp暂存null左右对调仍为null节点 3 的子节点均为空交换无实质变化2临界点触底回溯命中root null直接返回上一层节点 3 的两侧空节点处理完毕退出当前分支3节点 1进入dfs(root.right)左null, 右nulltemp暂存null左右对调仍为null节点 1 的子节点均为空交换无实质变化4临界点触底回溯命中root null直接返回上一层节点 1 的两侧空节点处理完毕退出当前分支5结束返回根节点root最终状态所有节点执行完毕触发return root;树结构已被完全物理重组返回新根节点五、 源码实现class Solution { public TreeNode invertTree(TreeNode root) { // 调用深度优先搜索函数对整棵树进行就地物理翻转 dfs(root); // 返回完成翻转后的根节点 return root; } private void dfs(TreeNode root) { // 边界安全检查若当前节点为空说明已越过叶子节点无需任何操作直接返回 if (root null) { return; } // 核心交换决策利用临时变量 temp 暂存左子节点指针 TreeNode temp root.left; // 将右子节点指针赋值给左子节点 root.left root.right; // 将暂存的左子节点指针赋值给右子节点完成当前节点的左右对调 root.right temp; // 纵向步进对当前新绑定的左子树继续执行深度优先翻转 dfs(root.left); // 纵向步进对当前新绑定的右子树继续执行深度优先翻转 dfs(root.right); } }六、 复杂度分析1. 时间复杂度O(n)分析算法采用标准的前序深度优先遍历模式。在递归执行过程中二叉树中的每一个节点都会且仅会被访问一次并在访问时执行常数级别O(1)的指针交换操作。结论总的操作基本次数与二叉树的节点总数n呈严格的线性正比关系即时间复杂度为O(n)。2. 空间复杂度O(height)分析该算法在运行期间仅就地修改指针没有申请任何与输入规模相关的外部数据结构。其空间消耗完全来自于递归调用时系统开辟的隐式函数栈。隐式栈的最大运行深度等于二叉树的最大高度height。在最坏情况下二叉树退化为单链表结构树高height等于n空间复杂度退化为O(n)。在最好情况下二叉树为完全二叉树或平衡二叉树树高height严格等于log n空间复杂度缩减为O(log n)。结论内存空间消耗在通用状态下定义为由树的几何形态决定的拓扑层级消耗即O(height)。