LeetCode 226 翻转二叉树Invert Binary Tree三种解法全解析BFS、递归 DFS 与迭代 DFS【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读翻转二叉树Invert Binary Tree是二叉树类题目中最经典的入门题之一其核心操作是将每个节点的左、右子树互换最终得到原树沿垂直轴对称的镜像树。本文以 LeetCode 226 为背景系统讲解三种实现思路基于队列的广度优先搜索BFS、基于递归的深度优先搜索DFS以及基于显式栈的迭代 DFS并对照本仓库 python/0226-invert-binary-tree.py 等多语言实现逐行剖析每个方案的直觉、算法步骤与复杂度。读完本文你将掌握二叉树镜像翻转的三种编码范式并能在面试中根据递归深度风险灵活选用迭代方案。前置知识解这道题之前需要掌握什么在动手写翻转二叉树的代码之前需要先具备以下四块基础能力它们分别对应了本文四种解法思路的底层支撑二叉树结构理解由val、left、right三部分构成的节点结构能够用递归或指针操作访问左右孩子广度优先搜索BFS掌握逐层遍历 队列的模式这是解法一的核心深度优先搜索DFS掌握递归式树遍历前序/中序/后序这是解法二的核心基于栈的迭代掌握如何用显式栈把递归 DFS 改写成迭代形式这是解法三的核心也是处理递归深度过大场景的关键手段。一、BFS逐层交换左右孩子直觉Intuition要翻转镜像一棵二叉树每个节点都必须交换它的left与right孩子。使用广度优先搜索BFS我们逐层处理整棵树从根节点出发对每个节点交换它的左右孩子然后把交换后的左右孩子入队持续处理直到所有节点都被访问过。这种方式保证每个节点恰好被访问一次并且在被遇到的当下就完成了翻转不需要额外的后处理。算法步骤若树为空直接返回null初始化一个队列并将root入队当队列非空时循环取出队首节点交换该节点的left和right孩子若left孩子存在将其入队若right孩子存在将其入队所有节点处理完毕后返回root即翻转后的树。多语言实现Pythonclass Solution: def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]: if not root: return None queue deque([root]) while queue: node queue.popleft() node.left, node.right node.right, node.left if node.left: queue.append(node.left) if node.right: queue.append(node.right) return rootJavapublic class Solution { public TreeNode invertTree(TreeNode root) { if (root null) { return null; } QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node queue.poll(); TreeNode temp node.left; node.left node.right; node.right temp; if (node.left ! null) { queue.offer(node.left); } if (node.right ! null) { queue.offer(node.right); } } return root; } }Cclass Solution { public: TreeNode* invertTree(TreeNode* root) { if (!root) return nullptr; queueTreeNode* queue; queue.push(root); while (!queue.empty()) { TreeNode* node queue.front(); queue.pop(); swap(node-left, node-right); if (node-left) queue.push(node-left); if (node-right) queue.push(node-right); } return root; } };JavaScriptclass Solution { invertTree(root) { if (root null) return null; const queue new Queue([root]); while (!queue.isEmpty()) { let node queue.pop(); [node.left, node.right] [node.right, node.left]; if (node.left ! null) queue.push(node.left); if (node.right ! null) queue.push(node.right); } return root; } }C#public class Solution { public TreeNode InvertTree(TreeNode root) { if (root null) return null; QueueTreeNode queue new QueueTreeNode(); queue.Enqueue(root); while (queue.Count 0) { TreeNode node queue.Dequeue(); TreeNode temp node.left; node.left node.right; node.right temp; if (node.left ! null) queue.Enqueue(node.left); if (node.right ! null) queue.Enqueue(node.right); } return root; } }Gofunc invertTree(root *TreeNode) *TreeNode { if root nil { return nil } queue : []*TreeNode{root} for len(queue) 0 { current : queue[0] queue queue[1:] current.Left, current.Right current.Right, current.Left if current.Left ! nil { queue append(queue, current.Left) } if current.Right ! nil { queue append(queue, current.Right) } } return root }Kotlinclass Solution { fun invertTree(root: TreeNode?): TreeNode? { if (root null) { return null } val queue: ArrayDequeTreeNode? ArrayDeque() queue.add(root) while (queue.isNotEmpty()) { val node queue.removeFirst() node?.let { val temp it.left it.left it.right it.right temp queue.add(it.left) queue.add(it.right) } } return root } }Swiftclass Solution { func invertTree(_ root: TreeNode?) - TreeNode? { guard let root root else { return nil } var queue DequeTreeNode() queue.append(root) while !queue.isEmpty { let node queue.removeFirst() (node.left, node.right) (node.right, node.left) if let left node.left { queue.append(left) } if let right node.right { queue.append(right) } } return root } }Rustimpl Solution { pub fn invert_tree(root: OptionRcRefCellTreeNode) - OptionRcRefCellTreeNode { if root.is_none() { return None; } let mut queue VecDeque::new(); queue.push_back(root.clone().unwrap()); while let Some(node) queue.pop_front() { let mut node_ref node.borrow_mut(); let left node_ref.left.take(); let right node_ref.right.take(); node_ref.left right; node_ref.right left; if let Some(ref l) node_ref.left { queue.push_back(l.clone()); } if let Some(ref r) node_ref.right { queue.push_back(r.clone()); } } root } }复杂度分析时间复杂度$O(n)$每个节点恰好入队、出队一次空间复杂度$O(n)$队列在最坏情况下完全二叉树的最后一层需要容纳约 $n/2$ 个节点。二、递归 DFS自上而下镜像整棵树直觉Intuition翻转二叉树本质上就是交换每个节点的左右子树。使用深度优先搜索DFS我们以自顶向下的方式递归翻转在每个节点处先交换左右孩子然后递归翻转左子树再递归翻转右子树。因为每一棵子树本身也是一棵更小的二叉树递归天然契合这种自相似结构。翻转发生在递归下潜的过程中每个子树最终都会被正确镜像。算法步骤若当前节点为null返回null交换该节点的left与right指针对新的left孩子递归调用dfs对新的right孩子递归调用dfs返回当前节点此时它已被翻转。注意步骤 3 与 4 递归的是交换之后的孩子引用这正是交换后引用会变化这一细节的体现。多语言实现Pythonclass Solution: def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]: if not root: return None root.left, root.right root.right, root.left self.invertTree(root.left) self.invertTree(root.right) return rootJavapublic class Solution { public TreeNode invertTree(TreeNode root) { if (root null) return null; TreeNode temp root.left; root.left root.right; root.right temp; invertTree(root.left); invertTree(root.right); return root; } }Cclass Solution { public: TreeNode* invertTree(TreeNode* root) { if (!root) return nullptr; swap(root-left, root-right); invertTree(root-left); invertTree(root-right); return root; } };JavaScriptclass Solution { invertTree(root) { if (!root) return null; [root.left, root.right] [root.right, root.left]; this.invertTree(root.left); this.invertTree(root.right); return root; } }C#public class Solution { public TreeNode InvertTree(TreeNode root) { if (root null) return null; TreeNode temp root.left; root.left root.right; root.right temp; InvertTree(root.left); InvertTree(root.right); return root; } }Gofunc invertTree(root *TreeNode) *TreeNode { if root nil { return nil } root.Left, root.Right root.Right, root.Left invertTree(root.Left) invertTree(root.Right) return root }Kotlinclass Solution { fun invertTree(root: TreeNode?): TreeNode? { if (root null) return null val temp root.left root.left root.right root.right temp invertTree(root.left) invertTree(root.right) return root } }Swiftclass Solution { func invertTree(_ root: TreeNode?) - TreeNode? { guard let root root else { return nil } (root.left, root.right) (root.right, root.left) invertTree(root.left) invertTree(root.right) return root } }Rustimpl Solution { pub fn invert_tree(root: OptionRcRefCellTreeNode) - OptionRcRefCellTreeNode { if let Some(node) root.as_ref() { let mut node_ref node.borrow_mut(); let left node_ref.left.take(); let right node_ref.right.take(); node_ref.left right; node_ref.right left; Self::invert_tree(node_ref.left.clone()); Self::invert_tree(node_ref.right.clone()); } root } }复杂度分析时间复杂度$O(n)$每个节点被访问一次空间复杂度$O(n)$来自递归调用栈树退化为链状时递归深度为 $n$。三、迭代 DFS用显式栈替代递归直觉Intuition迭代 DFS 使用显式栈代替递归来翻转二叉树核心思路与递归 DFS 完全一致访问一个节点交换它的左右孩子继续对其孩子执行同样的处理。区别在于不再依赖系统调用栈而是自己维护一个栈数据结构。执行流程如下将根节点压入栈弹出栈顶节点交换它的孩子若孩子存在将其压入栈重复直到栈为空。这种方式模拟了递归 DFS 的执行轨迹并且在递归深度可能过大例如树退化为链表时是更安全的选择。算法步骤若root为null返回null用root初始化一个栈当栈非空时循环弹出一个节点交换它的left与right指针若left孩子存在压入栈若right孩子存在压入栈返回root。多语言实现Pythonclass Solution: def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]: if not root: return None stack [root] while stack: node stack.pop() node.left, node.right node.right, node.left if node.left: stack.append(node.left) if node.right: stack.append(node.right) return rootJavapublic class Solution { public TreeNode invertTree(TreeNode root) { if (root null) return null; StackTreeNode stack new Stack(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); TreeNode temp node.left; node.left node.right; node.right temp; if (node.left ! null) stack.push(node.left); if (node.right ! null) stack.push(node.right); } return root; } }Cclass Solution { public: TreeNode* invertTree(TreeNode* root) { if (!root) return nullptr; stackTreeNode* stack; stack.push(root); while (!stack.empty()) { TreeNode* node stack.top(); stack.pop(); swap(node-left, node-right); if (node-left) stack.push(node-left); if (node-right) stack.push(node-right); } return root; } };JavaScriptclass Solution { invertTree(root) { if (!root) return null; const stack [root]; while (stack.length) { const node stack.pop(); [node.left, node.right] [node.right, node.left]; if (node.left) stack.push(node.left); if (node.right) stack.push(node.right); } return root; } }C#public class Solution { public TreeNode InvertTree(TreeNode root) { if (root null) return null; StackTreeNode stack new StackTreeNode(); stack.Push(root); while (stack.Count 0) { TreeNode node stack.Pop(); TreeNode temp node.left; node.left node.right; node.right temp; if (node.left ! null) stack.Push(node.left); if (node.right ! null) stack.Push(node.right); } return root; } }Kotlinclass Solution { fun invertTree(root: TreeNode?): TreeNode? { if (root null) return null root.left root.right.also { root.right root.left } invertTree(root.left) invertTree(root.right) return root } }Swiftclass Solution { func invertTree(_ root: TreeNode?) - TreeNode? { guard let root root else { return nil } var stack: [TreeNode] [root] while !stack.isEmpty { let node stack.removeLast() (node.left, node.right) (node.right, node.left) if let left node.left { stack.append(left) } if let right node.right { stack.append(right) } } return root } }Rustimpl Solution { pub fn invert_tree(root: OptionRcRefCellTreeNode) - OptionRcRefCellTreeNode { if root.is_none() { return None; } let mut stack vec![root.clone().unwrap()]; while let Some(node) stack.pop() { let mut node_ref node.borrow_mut(); let left node_ref.left.take(); let right node_ref.right.take(); node_ref.left right; node_ref.right left; if let Some(ref l) node_ref.left { stack.push(l.clone()); } if let Some(ref r) node_ref.right { stack.push(r.clone()); } } root } }注意上文中 Kotlin 的迭代版本利用also在一行内完成交换——root.right.also { ... }先保存旧右孩子再赋值旧左孩子最后把保存的右孩子赋给left是 Kotlin 语言特有的简洁写法。复杂度分析时间复杂度$O(n)$每个节点入栈、出栈一次空间复杂度$O(n)$显式栈最坏情况下需要存储一整层或整条链的节点。四、深入仓库源码三种解法的不同组织方式本仓库 leetcode 为本题提供了覆盖 14 种语言的参考实现LeetCode 226深入阅读这些文件可以发现除了上文文档中的交换 递归/迭代范式之外还存在两条等价的递归变体它们在面试中同样值得掌握。变体一先递归后交换后序式这类实现先递归翻转子树再把翻转后的子树互相交换等价于自底向上翻转java/0226-invert-binary-tree.java先递归得到翻转后的左右子树再将其挂到新构造的节点上node.right invertTree(root.left); node.left invertTree(root.right)以新建节点的方式返回新树go/0226-invert-binary-tree.go先保存invertTree(root.Left)的结果到临时变量再把invertTree(root.Right)赋给root.Left最后将临时变量赋给root.Right原地完成交换javascript/0226-invert-binary-tree.js同样先取left invertTree(root.left)、right invertTree(root.right)再执行root.left right; root.right leftrust/0226-invert-binary-tree.rs在borrow_mut的互斥借用范围内用take()取出左右孩子先递归翻转、后重新挂载返回nodec/0226-invert-binary-tree.c先递归得到inverted_right与inverted_left再交叉赋给左右指针swift/0226-invert-binary-tree.swift 与 kotlin/0226-invert-binary-tree.kt 也是同一范式。这种写法的好处是不会出现交换后引用混淆由于交换发生在递归返回之后递归调用始终使用翻转前稳定不变的孩子引用逻辑上更不易出错。变体二先交换后递归前序式文档主推先交换当前节点的左右孩子再递归处理交换后的孩子python/0226-invert-binary-tree.py 与 cpp/0226-invert-binary-tree.cpp 是这一范式的代表cpp 文件头部的注释还给出了示例root [4,2,7,1,3,6,9] - [4,7,2,9,6,3,1]方便直观验证翻转结果ruby/0226-invert-binary-tree.rb 额外做了一步叶子剪枝左右孩子均为nil时直接返回可视为一个小的提前返回优化dart/0226-invert-binary-tree.dart 与 csharp/0226-invert-binary-tree.cs 也采用先交换再递归的顺序。两种变体在结果上完全等价都能得到正确的镜像树差异仅在递归时机与代码组织方式。另外javascript/0226-invert-binary-tree.js 还同时收录了 BFS 版本并注明其空间复杂度为 $O(W)$$W$ 为树的最大宽度与本文第一部分的 BFS 方案互相印证。复杂度提示仓库 hints/invert-a-binary-tree.md 给出了本题的推荐目标以 $O(n)$ 时间、$O(n)$ 空间求解其中 $n$ 为树中节点数。三个方案均满足该目标其中 BFS 的空间复杂度受限于队列最大宽度 $O(W)$递归/迭代 DFS 则受限于树的深度 $O(H)$二者在最坏情况下都为 $O(n)$。五、常见陷阱与规避方法陷阱一没有处理空根节点忘记检查空根节点会导致空指针异常。无论采用哪种解法第一步都应当判断root是否为null若是则立即返回null或直接返回root见仓库中 go/0226-invert-binary-tree.go、c/0226-invert-binary-tree.c 等实现的写法。陷阱二交换后使用了错误的引用交换之后root.left指向的其实是原来的root.right。递归时如果仍按交换前的直觉去处理孩子就可能漏翻或重复翻转某些子树。正确做法是要么在递归调用时明确使用交换后的引用前序式要么先递归后交换后序式以避免歧义。陷阱三遍历过程中错误地修改结构在迭代方案中必须在交换之后再把孩子压入栈或队列如果在交换之前压入压入的引用位置随后会被改写导致处理到的节点不是预期的孩子从而产生错误结果。这一点对 BFS 的队列和迭代 DFS 的栈同样适用。总结翻转二叉树是一题三解的绝佳练习BFS 用队列逐层交换、递归 DFS 用系统调用栈自上而下交换、迭代 DFS 用显式栈模拟递归。三者时间复杂度均为 $O(n)$空间复杂度最坏均为 $O(n)$选择哪个方案取决于对递归深度的考量与个人编码习惯。结合本仓库 python/0226-invert-binary-tree.py 等 14 种语言的参考实现你既可以验证算法正确性也可以横向对比不同语言在指针交换、可选值Option/null处理上的语法差异从而把这道题吃透。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考