226. 翻转二叉树

解题思路

我们可以使用 递归 的方式来解决这个问题：

• 如果当前节点为空，直接返回 null。
• 否则，递归地翻转左子树和右子树。
• 然后交换当前节点的左右子节点。
• 最后返回当前节点（即翻转后的根）。

也可以用 迭代（BFS 或 DFS） 实现，但递归是最简洁直观的方式。

Java 代码实现（递归）

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 基本情况：如果节点为空，直接返回
        if (root == null) {
            return null;
        }

        // 递归翻转左右子树
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        // 交换左右子树
        root.left = right;
        root.right = left;

        return root;
    }
}

示例

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

时间复杂度 & 空间复杂度

• 时间复杂度：O(n)，其中 n 是树中节点的个数，每个节点都会被访问一次。
• 空间复杂度：O(h)，其中 h 是树的高度，主要是递归调用栈的深度。最坏情况下（退化为链表）为 O(n)，最好情况下（完全平衡）为 O(log n)。

下面是 迭代版本 的「翻转二叉树」实现。我们可以使用 栈（DFS） 或 队列（BFS） 来遍历所有节点，并在访问每个节点时交换它的左右子节点。

方法一：使用栈（模拟 DFS）

import java.util.*;

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            // 交换左右子节点
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;

            // 将非空子节点压入栈（顺序无所谓，因为只是遍历）
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }

        return root;
    }
}

方法二：使用队列（BFS，层序遍历）

import java.util.*;

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            // 交换左右子节点
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;

            // 将非空子节点加入队列
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        return root;
    }
}

说明

• 两种迭代方法本质相同：遍历所有节点 + 交换左右孩子。
• 区别仅在于遍历顺序：
  • 栈 → 深度优先（先处理子树深处）
  • 队列 → 广度优先（一层一层处理）
• 实际效果一样，最终整棵树都会被翻转。

复杂度分析（迭代版）

• 时间复杂度：O(n)，每个节点访问一次。
• 空间复杂度：O(w)，其中 w 是树的最大宽度（队列或栈的最大大小）。
  • 最坏情况（完全二叉树底层满）：O(n)
  • 平均情况：O(n/2) ≈ O(n)