226. 翻转二叉树

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. 算法流程 (递归三步曲)

1. 终止条件 (Base Case)：

• • root == null，空节点没法翻转，直接返回null。

1. 递归 (Recurse)：

• • left = invertTree(root.left)：先把左子树内部翻转好，并拿回来。
  • right = invertTree(root.right)：先把右子树内部翻转好，并拿回来。

1. 操作 (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

1. 递归到底: 此时root是 2。

• • invert(1)-> 返回 1。
  • invert(3)-> 返回 3。
  • Swap: 2 的左变 3，右变 1。返回(3-2-1)。

1. 递归到底: 此时root是 7。

• • invert(6)-> 返回 6。
  • invert(9)-> 返回 9。
  • Swap: 7 的左变 9，右变 6。返回(9-7-6)。

1. 回到根节点: 此时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

---