问题描述
翻转一棵二叉树，即将二叉树的每个节点的左右子树交换。翻转后，原二叉树的镜像对称结构将被呈现。
例如，原二叉树：
4
/ \
2 7
/ \ / \
1 3 6 9
翻转后变为：
4
/ \
7 2
/ \ / \
9 6 3 1
这个问题看似简单，却是理解二叉树遍历和递归分治思想的绝佳练习，也是许多面试的常考题目。
核心思路
方法一：递归分治（深度优先）
翻转一棵二叉树的递归思路非常直观：
- 基准情况：如果当前节点为
null，直接返回。 - 交换子树：交换当前节点的左子树和右子树。
- 递归处理：对交换后的左子树和右子树分别进行翻转。
这个思路体现了分治思想：将大问题（翻转整棵树）分解为两个相同的子问题（翻转左子树和翻转右子树），然后合并结果（交换左右子树）。
方法二：迭代层序遍历（广度优先）
使用队列按层遍历二叉树，对于每个出队的节点，交换其左右子节点，然后将非空的子节点入队继续处理。
完整Java实现
import java.util.LinkedList;
import java.util.Queue;
/**
* 翻转二叉树求解器
* 提供递归和迭代两种实现方式
*/
public class InvertBinaryTree {
/**
* 二叉树节点定义
*/
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* 方法一：递归分治（前序遍历思想）
* 时间复杂度: O(n)，空间复杂度: O(h) 其中h为树的高度
*
* 核心思想：先交换当前节点的左右子树，再递归翻转左右子树
*/
public TreeNode invertTreeRecursive(TreeNode root) {
// 基准情况：空节点无需翻转
if (root == null) {
return null;
}
// 第一步：交换当前节点的左右子节点
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 第二步：递归翻转左子树（注意：交换后原来的右子树变成了左子树）
invertTreeRecursive(root.left);
// 第三步：递归翻转右子树
invertTreeRecursive(root.right);
return root;
}
/**
* 递归的另一种写法：后序遍历思想
* 先递归翻转左右子树，再交换
*/
public TreeNode invertTreePostOrder(TreeNode root) {
if (root == null) {
return null;
}
// 先递归翻转左右子树
TreeNode left = invertTreePostOrder(root.left);
TreeNode right = invertTreePostOrder(root.right);
// 再交换当前节点的左右子树
root.left = right;
root.right = left;
return root;
}
/**
* 方法二：迭代层序遍历（BFS）
* 时间复杂度: O(n)，空间复杂度: O(w) 其中w为树的最大宽度
*
* 使用队列按层处理每个节点，交换其左右子节点
*/
public TreeNode invertTreeIterative(TreeNode root) {
if (root == null) {
return null;
}
// 使用LinkedList作为队列
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 按层遍历
while (!queue.isEmpty()) {
// 取出当前节点
TreeNode current = queue.poll();
// 交换当前节点的左右子节点
TreeNode temp = current.left;
current.left = current.right;
current.right = temp;
// 将非空的子节点加入队列，继续处理下一层
if (current.left != null) {
queue.offer(current.left);
}
if (current.right != null) {
queue.offer(current.right);
}
}
return root;
}
/**
* 方法三：迭代深度优先（使用栈模拟递归）
* 时间复杂度: O(n)，空间复杂度: O(h)
*/
public TreeNode invertTreeStack(TreeNode root) {
if (root == null) {
return null;
}
// 使用栈模拟递归的深度优先遍历
LinkedList<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode current = stack.pop();
// 交换左右子节点
TreeNode temp = current.left;
current.left = current.right;
current.right = temp;
// 先将左子节点入栈（后入先出，保证先处理右子树）
if (current.left != null) {
stack.push(current.left);
}
if (current.right != null) {
stack.push(current.right);
}
}
return root;
}
/**
* 辅助方法：构建示例二叉树
* 4
* / \
* 2 7
* / \ / \
* 1 3 6 9
*/
public static TreeNode buildSampleTree() {
TreeNode node1 = new TreeNode(1);
TreeNode node3 = new TreeNode(3);
TreeNode node6 = new TreeNode(6);
TreeNode node9 = new TreeNode(9);
TreeNode node2 = new TreeNode(2, node1, node3);
TreeNode node7 = new TreeNode(7, node6, node9);
return new TreeNode(4, node2, node7);
}
/**
* 辅助方法：按层序打印二叉树（用于验证结果）
*/
public static void printTreeLevelOrder(TreeNode root) {
if (root == null) {
System.out.println("null");
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
System.out.print("层序遍历: ");
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
if (current != null) {
System.out.print(current.val + " ");
queue.offer(current.left);
queue.offer(current.right);
} else {
System.out.print("null ");
}
}
System.out.println();
}
/**
* 辅助方法：中序遍历打印（用于观察结构变化）
*/
public static void printInOrder(TreeNode root) {
if (root == null) return;
printInOrder(root.left);
System.out.print(root.val + " ");
printInOrder(root.right);
}
public static void main(String[] args) {
InvertBinaryTree solution = new InvertBinaryTree();
System.out.println("===== 翻转二叉树测试 =====\n");
// 测试递归方法
TreeNode tree1 = buildSampleTree();
System.out.print("翻转前中序: ");
printInOrder(tree1);
System.out.println();
solution.invertTreeRecursive(tree1);
System.out.print("翻转后中序: ");
printInOrder(tree1);
System.out.println();
// 测试迭代BFS方法
TreeNode tree2 = buildSampleTree();
System.out.print("\n翻转前层序: ");
printTreeLevelOrder(tree2);
solution.invertTreeIterative(tree2);
System.out.print("翻转后层序: ");
printTreeLevelOrder(tree2);
// 测试栈方法
TreeNode tree3 = buildSampleTree();
System.out.print("\n翻转前中序: ");
printInOrder(tree3);
System.out.println();
solution.invertTreeStack(tree3);
System.out.print("翻转后中序: ");
printInOrder(tree3);
System.out.println();
}
}
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 递归（前序/后序） | O(n) |
O(h) |
代码简洁，最常用 |
| 迭代BFS（队列） | O(n) |
O(w) |
按层处理，直观 |
| 迭代DFS（栈） | O(n) |
O(h) |
避免递归栈溢出风险 |
其中 n 为节点总数，h 为树的高度，w 为树的最大宽度。
扩展思考
- 判断对称二叉树：翻转二叉树后与原树比较，如果相同则是对称的。
- 二叉树的镜像比较：给定两棵二叉树，判断它们是否互为镜像。
- N叉树的翻转：将思路扩展到每个节点有多个子节点的场景，依次反转子节点列表。
- 路径相关的翻转：只翻转满足特定条件（如路径和为某值）的子树。
可视化过程
以递归前序遍历为例，翻转过程的调用栈如下：
invertTree(4)
交换 2 和 7
invertTree(7)
交换 6 和 9
invertTree(9) -> 返回
invertTree(6) -> 返回
invertTree(2)
交换 1 和 3
invertTree(3) -> 返回
invertTree(1) -> 返回
总结
翻转二叉树是理解树形递归与分治思想的经典问题。递归方案利用函数调用栈隐式地保存了遍历状态，代码最为简洁；迭代方案则使用显式数据结构（队列或栈），更适合处理深度极大的树以避免栈溢出。掌握这两种思路，可以帮助我们更好地理解二叉树的各种遍历算法。
