226. 二叉树翻转#

树的镜像：生活中的启示#

想象你站在一面魔法镜前，树木在镜子中神奇地翻转。左变右，上变下，整个世界仿佛瞬间颠倒，却保持着原有的结构和精髓。这正是二叉树翻转的本质 —— 一种保持根本不变，却完全重构的奇妙变换。

问题描述#

题目目标#

给你一棵二叉树的根节点 root ，请你翻转这棵二叉树，并返回其根节点。

示例 1#

输入： root = [4,2,7,1,3,6,9] 输出： [4,7,2,9,6,3,1] 二叉树示意：

text

说明： 把每个节点的左右子树交换后，就得到输出中的镜像结构。

补充说明#

二叉树通常使用层序数组表示，null 表示该位置没有节点。

翻转的本质：节点的镜像重构#

二叉树翻转（LeetCode第226题）意味着对于树中的每个节点，我们交换其左右子树。这个过程就像是给树木穿上镜面外衣，保持原有节点值不变，但改变它们的空间布局。

翻转的三个关键步骤#

交换当前节点的左右子树
递归地翻转左子树
递归地翻转右子树

递归解法：代码中的镜像魔法#

public TreeNode invertTree(TreeNode root) {
    // 递归终止条件：空节点无需翻转，直接返回
    if (root == null) return null;

    // 先暂存原左子树，避免后续赋值覆盖
    TreeNode leftSubtree = root.left;
    // 把“翻转后的原右子树”挂到当前节点左边
    root.left = invertTree(root.right);
    // 把“翻转后的原左子树”挂到当前节点右边
    root.right = invertTree(leftSubtree);

    // 返回当前子树翻转后的根节点
    return root;
}

java

代码解析：每一行的深层思考#

if (root == null) return null;
- 递归的安全阀
- 处理空树或遍历到叶子节点的边界情况
TreeNode leftSubtree = root.left;
- 在交换前先保存左子树
- 防止左子树信息在第一次赋值时丢失
root.left = invertTree(root.right);
- 将右子树（经过翻转）赋值给左子树位置
- 递归调用确保子树也被完整翻转
root.right = invertTree(leftSubtree);
- 将原左子树（经过翻转）赋值给右子树位置
- 完成当前节点的镜像重构

迭代方法：显式控制的翻转之旅#

public TreeNode invertTree(TreeNode root) {
    // 边界处理：空树直接返回
    if (root == null) return null;

    // 用队列进行层序遍历，逐个节点交换左右孩子
    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;
}

java

迭代方法的独特视角#

使用队列进行显式的层序遍历
每次弹出一个节点，就地交换其左右子树
通过队列管理遍历的”进度”
避免了递归可能导致的栈溢出风险

性能分析：时间与空间的博弈#

时间复杂度：O(n)#

每个节点仅访问一次
n为树中节点总数
无论递归还是迭代，都高效地遍历整棵树

空间复杂度#

递归版本：O(h)，h为树的高度
- 最坏情况可达O(n)
- 最好情况（平衡树）为O(log n)
迭代版本：O(w)，w为树的最大宽度
- 通常空间效率更高

思考与拓展#

为什么交换左右子树就完成了树的镜像？
如何处理不同类型的二叉树翻转？
这种翻转对树的其他性质有何影响？

实际应用场景#

图像处理中的对称变换
计算机图形学的镜像效果
二叉树算法的对称性研究
数据可视化中的布局重构

深度思考：递归的诗与逻辑#

翻转二叉树不仅仅是一道算法题，更是递归思想的诗意展现。它启示我们：

复杂问题可以通过相似的小问题逐步解决
递归是一种强大的思维工具
代码的优雅源于思维的清晰和简洁

记住，翻转二叉树就像在知识的镜子中探索对称与变换，重要的是保持好奇和开放的心态！