--- tags: ["LeetCode", "二叉树", "深度优先搜索", "广度优先搜索", "递归", "迭代", "简单"] create time: 2026-05-17 10:45 --- # 38-翻转二叉树 ## 题面 给你一棵二叉树的根节点 `root`，**翻转**这棵二叉树，并返回其根节点。 > [!question] 💡 什么是「翻转」？ > 翻转的意思是：**交换每个节点的左右子树**。换句话说，把整棵树沿中线做一面镜子，左变右、右变左。 > > > [!note] 🪞 直观理解 > > - 叶子节点：没有子节点，翻转后不变 > > - 中间节点：左右子树互换位置 > > - 翻转作用于**每一个**节点，从根一直到底 **示例 1：** ``` 输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1] 原始树 翻转后 4 4 / \ / \ 2 7 → 7 2 / \ / \ / \ / \ 1 3 6 9 9 6 3 1 ``` **示例 2：** ``` 输入：root = [2,1,3] 输出：[2,3,1] 2 2 / \ → / \ 1 3 3 1 ``` **示例 3：** ``` 输入：root = [] 输出：[] 空树翻转后仍是空树 ``` **约束：** - 树中节点数目范围在 `[0, 100]` 内 - `-100 <= Node.val <= 100` --- ## 思路 ### 方法一：深度优先搜索 DFS（递归）⭐⭐ #### 核心洞察 > [!question] 🤔 思考 > 如果你手里拿着一个节点，要翻转以它为根的这棵子树，你最需要做的动作是什么？ 答案其实只有一个：**交换它的左右孩子**——就这么简单！ 但要注意，交换完之后，左右孩子本身可能还挂着更深的子树，所以还需要**递归地对它们的子树也做同样的操作**。 这就是分而治之的思想：把「翻转整棵树」分解为「翻转每棵子树」，每个子树只做一件事——交换左右孩子。 #### 递归三要素 | 要素 | 内容 | |------|------| | **终止条件** | 节点为空时，直接返回（空树无需翻转） | | **执行动作** | 交换 `node.Left` 和 `node.Right` | | **递归调用** | 对交换后的左右子节点分别递归翻转 | #### 执行流程图解 以示例 1 的原始树为例，展示递归如何逐层深入、逐层完成翻转： ``` 4 4 4 / \ / \ / \ 2 7 → 7 2 → 7 2 / \ / \ / \ / \ / \ / \ 1 3 6 9 9 6 3 1 9 6 3 1 ↑ ↑ ↑ 步骤3 步骤2 步骤1 (叶子不变) (7的孩⼦换位置) (根节点先换⼿) ⾃顶向下递归（前序）：先交换再递归孩⼦ ``` ```mermaid flowchart TD S["dfs(4)\n先交换 4 的孩⼦"] --> L["dfs(7)\n交换 7 的孩⼦"] L --> L1["dfs(nil) → nil\n⽆需翻转"] L --> R1["dfs(nil) → nil\n⽆需翻转"] L1 --> L2["返回 {6, 3}\n7的孩⼦已翻转✅"] R1 --> L2 L2 --> M["dfs(2)\n交换 2 的孩⼦"] M --> L3["dfs(9)\n返回{6, nil}✅"] M --> R2["dfs(nil) → nil\n返回{3}✅"] L3 --> M2["返回{1,3}\n2的孩⼦已翻转✅"] R2 --> M2 M2 --> E["dfs(4)\n左=翻转后{7}, 右=翻转后{2}\n根节点完成✅🎉"] style E fill:#d4edda,stroke:#28a745,stroke-width:3px style M fill:#cce5ff,stroke:#004085 style L fill:#fff3cd,stroke:#856404 ``` #### Go 语言的优雅写法 Go 支持多值赋值，可以直接用一行完成交换，无需临时变量： ```go // ❌ 常规写法（需要临时变量） tmp := node.Left node.Left = node.Right node.Right = tmp // ✅ Go 风格（并行交换） node.Left, node.Right = node.Right, node.Left ``` > [!tip] 🔑 多值赋值的奥秘 > Go 的多值赋值是**先求值再赋值**——等号右边的表达式全部计算完毕后，再同时赋给左边。这意味着 `node.Left, node.Right = node.Right, node.Left` 等价于先用临时变量交换，不会先覆盖再出错。 #### 一步到位版（最简递归） 既然交换完左右子节点后，我们只需要让它们各自被翻转，那就可以把递归调用写在等号右边，直接赋值回去： ``` invertTree(node): if node == nil: return nil // 递归结果直接作为新的左右孩子 node.Left = invertTree(node.Right) // 原来的右子树翻转变左 node.Right = invertTree(node.Left) // 原来的左子树翻转变右 return node ``` > [!warning] ⚠️ 这和显式交换等价吗？ > **完全等价！** 注意 Go 多值赋值的特性：`node.Left = invertTree(node.Right)` 执行时，`node.Left` 的值已经作为参数传入右侧函数了，虽然这里我们把 `node.Right` 的返回值赋给了 `node.Left`……等等，这里似乎有问题？ > > 实际上这种写法**有 bug**！第一行执行完后 `node.Left` 已经被修改了，第二行 `invertTree(node.Left)` 翻转的是新左子树而非原左子树。 > > 正确的单行写法是用 Go 多值赋值： ```go node.Left, node.Right = invertTree(node.Right), invertTree(node.Left) ``` > [!note] ⚡ 多值赋值的正确用法 > 上面的两行依次赋值写法是错误的（除非你确认左侧递归不依赖原值），但在 Go 中以下写法是正确的——因为多值赋值的右侧先全部求值完毕： > > ```go > node.Left, node.Right = invertTree(node.Right), invertTree(node.Left) > ``` > > 这是最简洁的「翻转+递归+返回」三合一写法。 ### 方法二：广度优先搜索 BFS（层序遍历迭代）⭐ #### 核心思想 BFS 按层访问节点。**对于每一层的每个节点，交换其左右孩子即可。** 这种方式的优点是过程非常直观：从左到右、从上到下扫一遍，每到一课就翻一次。 ```mermaid flowchart LR A["第 1 层: [4]\n交换 4 的左右孩子"] --> B["第 2 层: [7,2]\n交换 7 和 2 的孩子"] B --> C["第 3 层: [9,6,3,1]\n都是叶子,交换无变化"] C --> D["遍历结束 ✅\n返回 root"] style A fill:#e8f5e9 style B fill:#fff3e0 style C fill:#e3f2fd style D fill:#fce4ec ``` #### 算法骨架 ``` if root == nil: return nil queue = [root] while queue 非空: node = pop(queue) swap(node.left, node.right) // 核心动作 if node.left != nil: push(queue, node.left) if node.right != nil: push(queue, node.right) return root ``` ### 方法三：深度优先搜索 DFS（迭代）⭐ 除了 BFS 逐层翻转，DFS 也可以用显式栈来模拟递归过程。 > [!comparison] ⚖️ 三种写法对比 > | 维度 | DFS 递归 | BFS 迭代 | DFS 迭代 | > |------|---------|---------|---------| > | 代码简洁度 | ⭐⭐⭐ 仅需 4 行 | ⭐⭐ 需维护队列 | ⭐⭐ 需维护栈 | > | 空间复杂度 | O(h) 递归栈 | O(w) 队列最大宽度 | O(h) 栈深度 | > | 遍历顺序 | 前序（根→左→右） | 逐层（自顶向下） | 前序（自定义） | > | 面试推荐度 | **首选** | 直观易懂 | 展示底层理解 | > [!tip] 🔑 为什么 DFS 递归天然使用前序？ > 因为我们在深入子树**之前**就先做了交换动作（visit node first），所以是前序遍历的顺序。事实上，翻转可以在任何遍历时机进行——前序、中序、后序都可以完成翻转，最终结果是一样的。前序是最直观的：当前节点都交换完了再去孩子那里。 --- ## 代码提示 ### DFS 递归伪代码 ``` func invertTree(node): if node == nil: return nil // 递归翻转右子树和左子树，然后交换赋值 node.Left, node.Right = invertTree(node.Right), invertTree(node.Left) return node ``` ### BFS 迭代伪代码 ``` if root == nil: return nil queue = [root] while len(queue) > 0: node = pop(queue) swap(node.left, node.right) if node.left != nil: push(queue, node.left) if node.right != nil: push(queue, node.right) return root ``` --- ## 技巧 > [!tip] 🔑 翻转的遍历时机不影响结果 > 无论是前序、中序还是后序遍历，只要在每个节点上执行 swap(left, right)，最终翻转的结果都是一样的。这是因为翻转只关注"每个孩子节点都会被访问且交换一次"，与访问顺序无关。 > > 但中序遍历需要小心！如果在交换后再走右边，原本的右子树现在已经变成了左子树，容易漏掉或重复处理。实际写起来比前/后序复杂。 > [!tip] 🔑 Go 多值赋值是杀手锏 > `node.Left, node.Right = node.Right, node.Left` 这一行同时完成了交换和简洁表达，是 Go 语言实现翻转的经典范式。 > [!info] 📊 复杂度速查 > | 方法 | 时间复杂度 | 空间复杂度 | > |------|-----------|-----------| > | DFS 递归 | **O(n)** — 每个节点访问一次 | **O(h)** — h 为树高，最坏 O(n)（链状），平均 O(log n)（平衡树） | > | BFS 迭代 | **O(n)** — 每个节点入队出队各一次 | **O(w)** — w 为树的最大宽度，满二叉树最后一层最多 (n+1)/2 个节点 | > | DFS 迭代 | **O(n)** | **O(h)** | > [!note] 🧩 延伸思考 > - **对称二叉树**（LeetCode 101）：判断一棵树是否是它自己的镜像。思路和翻转高度相关——如果一棵树翻转后等于自身，它就是对称的。 > - **最小/最大深度**（LeetCode 104/111）：同样是经典的二叉树基础题，可对比练习。 > - **N 叉树翻转**：思路完全一致，只是把孩子切片反转而非交换两个指针。 --- ## 代码 ### DFS 递归法（推荐）⭐⭐ ```go /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func invertTree(root *TreeNode) *TreeNode { // 终止条件：空节点不需要翻转 if root == nil { return nil } // Go 多值赋值：右侧先全部求值，再同时赋给左侧 // 等价于：先把右子树翻转后变成新左孩子，左子树翻转后变成新右孩子 root.Left, root.Right = invertTree(root.Right), invertTree(root.Left) return root } ``` > [!success] ✅ 运行验证 > 这是 LeetCode 第 226 题，通过率约 95%（Easy 中最高的题目之一）。代码仅 4 行核心逻辑，完美展示了递归的威力：**定义函数语义 → 假设子问题已解决 → 只需处理当前层**。 ### BFS 层序遍历法（参考）⭐ ```go /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func invertTree(root *TreeNode) *TreeNode { if root == nil { return nil } var queue []*TreeNode // 使用切片模拟队列 queue = append(queue, root) for len(queue) > 0 { node := queue[0] // 出队 queue = queue[1:] // 交换左右子节点 node.Left, node.Right = node.Right, node.Left if node.Left != nil { queue = append(queue, node.Left) } if node.Right != nil { queue = append(queue, node.Right) } } return root } ``` > [!note] 🐹 Go 切片队列注意事项 > 上述 BFS 中使用 `queue = queue[1:]` 出队，随着循环进行切片头部不断缩小，底层数组无法释放。虽然在本题数据范围（≤ 100 节点）下毫无压力，但如果节点数量很大，建议使用双索引方式避免内存泄漏： > > ```go > head := 0 > for head < len(queue) { > node := queue[head] > head++ > // ... 处理后追加新元素，queue 只会增长不会缩容 > } > ```