企业官网建设流程全解析

LeetCode-Book 实战解析：226. 翻转二叉树（二叉树镜像）的递归与迭代实现

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

本篇技术指南以 selected_coding_interview/docs/226. 翻转二叉树.md 为核心骨架，系统讲解「翻转二叉树（Invert Binary Tree）」这道经典二叉树题目：从二叉树镜像的数学定义出发，给出递归法与辅助栈/队列迭代法两种解法，并对照当前仓库 LeetCode-Book 中selected_coding_interview/codes下 Python、Java、C++ 三语言的可运行实现，帮助你掌握树形结构的遍历与原地改造能力，为后续二叉搜索树、最近公共祖先等题目打下基础。

题目回顾：什么是翻转二叉树

LeetCode 226「翻转二叉树」要求：给定一棵二叉树的根节点root，翻转这棵二叉树，并返回其根节点。所谓"翻转"，本质上就是求二叉树的镜像。

二叉树镜像定义：对于二叉树中任意节点root，设其左 / 右子节点分别为left, right；则在二叉树的镜像中，对应root节点的左 / 右子节点分别为right, left。

原始二叉树 翻转后的二叉树（镜像） 4 4 / \ / \ 2 7 7 2 / \ / \ / \ / \ 1 3 6 9 9 6 3 1

直观地看，翻转操作就是逐节点交换左右子树，并把交换的动作递归地施加到每一棵子树，最终整棵树水平对称反转。由于该题解法思路清晰、覆盖了递归与迭代两类基本树遍历范式，它既是面试高频题，也是理解更复杂树操作的入门跳板。

方法一：递归法（深度优先遍历）

根据二叉树镜像的定义，递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。

递归解析

1. 终止条件：当节点root为空时（即越过叶节点），返回null。
2. 递推工作：
   • 初始化节点tmp，用于暂存root的左子节点；
   • 开启递归右子节点invertTree(root.right)，并将返回值作为root的左子节点；
   • 开启递归左子节点invertTree(tmp)，并将返回值作为root的右子节点。
3. 返回值：返回当前节点root。

关键问题：为何需要暂存左子节点？

Q：为何需要暂存root的左子节点？A：在递归右子节点root.left = invertTree(root.right);执行完毕后，root.left的值已经发生改变，此时再递归左子节点invertTree(root.left)则会出错。

如果先执行root.left = invertTree(root.right)，那么root的左指针已经被右子树的递归结果覆盖，原始左子树连同其引用一起丢失；后续再对"新的左子节点"递归，翻转的将是错误的子树。因此必须先用tmp保存原始左子节点，等右子树翻转完成后，再对tmp（原始左子树）递归。

三语言代码实现

Python（显式暂存）：

class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return tmp = root.left root.left = self.invertTree(root.right) root.right = self.invertTree(tmp) return root

Python（平行赋值写法，无需暂存）：

Python 支持平行赋值（a, b = b, a），可省略暂存操作。其原理是先将等号右侧打包成元组(b, a)，再序列地分给等号左侧的a, b，因此在赋值发生前右侧的两个值已被完整求值，天然规避了覆盖问题：

class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return root.left, root.right = self.invertTree(root.right), self.invertTree(root.left) return root

Java：

class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode tmp = root.left; root.left = invertTree(root.right); root.right = invertTree(tmp); return root; } }

C++：

class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root == nullptr) return nullptr; TreeNode* tmp = root->left; root->left = invertTree(root->right); root->right = invertTree(tmp); return root; } };

复杂度分析

• 时间复杂度 $O(N)$：其中 $N$ 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 $O(N)$ 时间。
• 空间复杂度 $O(N)$：最差情况下（当二叉树退化为链表，即每个节点只有一个子节点时），递归深度达到 $N$，系统需使用 $O(N)$ 大小的栈空间；平均/最好情况下为 $O(\log N)$。

方法二：辅助栈（或队列）迭代法

利用栈（或队列）遍历树的所有节点node，并交换每个node的左 / 右子节点。相比递归，该方法不使用系统调用栈，逻辑完全由显式数据结构驱动。

算法流程

1. 特例处理：当root为空时，直接返回null。
2. 初始化：栈（或队列），本文用栈，并加入根节点root。
3. 循环交换：当栈stack为空时跳出循环：
   • 出栈：弹出栈顶节点记为node；
   • 添加子节点：将node的左、右子节点依次入栈（非空才入栈）；
   • 交换：交换node的左 / 右子节点。
4. 返回值：返回根节点root。

三语言代码实现

Python（利用平行赋值简化交换）：

class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return stack = [root] while stack: node = stack.pop() if node.left: stack.append(node.left) if node.right: stack.append(node.right) node.left, node.right = node.right, node.left return root

Java：

class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return null; Stack<TreeNode> stack = new Stack<>() {{ add(root); }}; while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node.left != null) stack.add(node.left); if (node.right != null) stack.add(node.right); TreeNode tmp = node.left; node.left = node.right; node.right = tmp; } return root; } }

C++：

class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root == nullptr) return nullptr; stack<TreeNode*> stack; stack.push(root); while (!stack.empty()) { TreeNode* node = stack.top(); stack.pop(); if (node->left != nullptr) stack.push(node->left); if (node->right != nullptr) stack.push(node->right); TreeNode* tmp = node->left; node->left = node->right; node->right = tmp; } return root; } };

变体提示：若把上述栈替换为队列（collections.deque/LinkedList/std::queue），遍历顺序变为层序（BFS），但交换逻辑完全相同——因为翻转只要求"每个节点都完成左右子节点交换"，与访问顺序无关，栈、队列两种容器均可正确求解。

复杂度分析

• 时间复杂度 $O(N)$：其中 $N$ 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 $O(N)$ 时间。
• 空间复杂度 $O(N)$：最差情况下（完全二叉树），栈stack最多同时存储 $\frac{N + 1}{2}$ 个节点（即最后一层的节点数），占用 $O(N)$ 额外空间。

仓库实践：可运行代码与测试驱动

原文档给出的是 LeetCode 在线判题环境下的核心解法代码；在 LeetCode-Book 仓库中，同一道题被组织为可直接编译运行、自带测试用例与驱动代码的完整工程，位于 selected_coding_interview/codes 目录：

以 Python 递归版 lc_226_invert_binary_tree_s1.py 为例，文件由三部分构成：

from include import * # 引入 TreeNode、list_to_tree 等工具 # ===== Solution Code ===== class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return tmp = root.left root.left = self.invertTree(root.right) root.right = self.invertTree(tmp) return root # ======= Test Case ======= # Test case 1: Basic binary tree root = list_to_tree([3, 9, 20, None, None, 15, 7]) # ====== Driver Code ====== slt = Solution() result = slt.invertTree(root) print(result)

其中：

• Solution Code与文档解法一一对应，可直接复制到 LeetCode 提交；
• Test Case通过list_to_tree将层序数组（None表示空节点）构造为二叉树，其实现位于 binary_tree.py：内部用collections.deque做层序建树，TreeNode的定义（val/left/right三个字段）也在此文件中；
• Driver Code实例化Solution并调用invertTree，直接python lc_226_invert_binary_tree_s1.py即可运行验证。

Java 与 C++ 版本结构类似：Java 通过TreeNode.arrToTree(new Integer[]{3, 9, 20, null, null, 15, 7})构造测试用例；C++ 使用vectorToTree({4, 2, 7, 1, 3, 6, 9})构造，并调用PrintUtil::printTree以可视化形式打印翻转后的树结构，方便直接观察结果。

延伸思考与关联题目

1. 翻转与对称的关系：翻转二叉树与「对称二叉树」（101. 对称二叉树.md）互为镜像操作——对一棵树翻转后再判断是否与自身相同，等价于判断其是否左右对称。同一思路也出现在剑指 Offer 的「二叉树的镜像」一题中，仓库的 leetbook_ioa 部分以 LCR 144. 翻转二叉树.md 收录了同题解法，可作为配套练习。
2. 递归与迭代的选型：递归写法简洁、可读性强，但最差情况下递归深度为 $O(N)$，对极深链表型树存在栈溢出风险；迭代法用显式栈/队列替代系统调用栈，适合对空间占用有严格要求的场景。
3. 平行赋值技巧的通用性：Python 平行赋值避免了显式tmp，但其本质仍是"先求值、后赋值"，理解这一点对调试其他需要交换/覆盖的场景很有帮助。

小结

翻转二叉树是树结构入门必会题：递归法体现"分治"思想，先翻转子树再组装当前节点；辅助栈/队列迭代法体现"显式遍历 + 原地改造"的工程思维。两者时间复杂度均为 $O(N)$，空间复杂度最差 $O(N)$。结合 LeetCode-Book 仓库中 Python、Java、C++ 三语言可运行实现，你可以在本地直接复现并验证算法正确性，为攻克二叉树家族的进阶题目（层序遍历、最近公共祖先、序列化等）打下坚实基础。

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book