226. 翻转二叉树
简单
给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]示例 2：
输入：root = [2,1,3] 输出：[2,3,1]示例 3：
输入：root = [] 输出：[]提示：
- 树中节点数目范围在
[0, 100]内 -100 <= Node.val <= 100
📝 核心笔记：翻转二叉树 (Invert Binary Tree)
1. 核心思想 (一句话总结)
“照镜子：对于树中的每一个节点，都要交换它的左胳膊和右胳膊。”
- 翻转二叉树并不是只翻转根节点的左右，而是要递归地深入到每一个子节点，把它们的左右孩子也都交换了。
- 最终效果是整个树变成了镜像。
2. 算法流程 (递归三步曲)
- 终止条件 (Base Case)：
root == null，空节点没法翻转，直接返回null。
- 递归 (Recurse)：
left = invertTree(root.left)：先把左子树内部翻转好，并拿回来。right = invertTree(root.right)：先把右子树内部翻转好，并拿回来。
- 操作 (Swap)：
- 关键动作：
root.left = right,root.right = left。 - 将“处理好的右子树”挂到左边，将“处理好的左子树”挂到右边。
- 关键动作：
🔍 代码回忆清单
// 题目：LC 226. Invert Binary Tree class Solution { public TreeNode invertTree(TreeNode root) { // 1. 终止条件 if (root == null) { return null; } // 2. 递归处理子节点 (后序遍历视角) // 就像外包一样，先让手下把左右两边的家务事处理好 TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); // 3. 交换当前节点的左右指针 // 手下处理完了，老板把自己左右手交换一下 root.left = right; root.right = left; return root; } }⚡ 快速复习 CheckList (易错点 & 扩展)
- [ ]先交换还是先递归？
- 都可以！
- 后序 (您的写法)：先递归到底，由下往上交换。
- 前序：先交换
root.left和root.right，然后再递归invertTree(root.left)和root.right。 - 中序：比较麻烦，因为交换完左边后，原来的右边变成了左边，如果再递归右边，其实是在递归“原来的左边”。需要小心处理。建议面试只写前序或后序。
- [ ]能不能用 BFS (层序遍历)？
- 面试加分项。可以！
- 把节点放入队列。每次取出一个节点，交换它的左右孩子，然后把左右孩子扔进队列。这样也能一层层完成翻转。
- [ ]必须返回值吗？
- 题目要求返回
TreeNode，所以递归函数最后要return root。
- 题目要求返回
🖼️ 数字演练
树结构：
4 / \ 2 7 / \ / \ 1 3 6 9- 递归到底: 此时
root是 2。
invert(1)-> 返回 1。invert(3)-> 返回 3。- Swap: 2 的左变 3，右变 1。返回(3-2-1)。
- 递归到底: 此时
root是 7。
invert(6)-> 返回 6。invert(9)-> 返回 9。- Swap: 7 的左变 9，右变 6。返回(9-7-6)。
- 回到根节点: 此时
root是 4。
left拿到了 (3-2-1)。right拿到了 (9-7-6)。- Swap: 4 的左接 (9-7-6)，右接 (3-2-1)。
Result:
4 / \ 7 2 / \ / \ 9 6 3 1
)