翻转二叉树的 Java 实现

1. 概述

✅ 翻转二叉树是技术面试中常见的题目之一，虽然实现不复杂，但能考察对递归和树结构的理解。

本文将介绍两种实现方式：递归和迭代，适合有一定算法基础的开发者快速回顾。

2. 二叉树结构

二叉树是一种每个节点最多有两个子节点的数据结构，通常称为左子节点（left child）和右子节点（right child）。树的顶层节点称为根节点（root node），中间的节点称为内部节点（interior node），没有子节点的节点称为叶子节点（leaf node）。

我们先定义一个表示节点的类：

public class TreeNode {

    private int value;
    private TreeNode rightChild;
    private TreeNode leftChild;

    // 构造方法、Getter 和 Setter 省略
}

接下来构建一个示例二叉树用于演示：

TreeNode leaf1 = new TreeNode(1);
TreeNode leaf2 = new TreeNode(3);
TreeNode leaf3 = new TreeNode(6);
TreeNode leaf4 = new TreeNode(9);

TreeNode nodeRight = new TreeNode(7, leaf3, leaf4);
TreeNode nodeLeft = new TreeNode(2, leaf1, leaf2);

TreeNode root = new TreeNode(4, nodeLeft, nodeRight);

该代码构建的原始二叉树结构如下图所示：

翻转后，二叉树的左右子树交换，结构如下：

3. 翻转二叉树的实现

3.1 递归法

✅ 递归是最直观的实现方式。

思路是：从根节点开始，交换当前节点的左右子节点，然后递归处理左右子树。

public void reverseRecursive(TreeNode treeNode) {
    if (treeNode == null) {
        return;
    }

    // 交换左右子节点
    TreeNode temp = treeNode.getLeftChild();
    treeNode.setLeftChild(treeNode.getRightChild());
    treeNode.setRightChild(temp);

    // 递归处理左右子树
    reverseRecursive(treeNode.getLeftChild());
    reverseRecursive(treeNode.getRightChild());
}

⚠️ 优点：代码简洁，逻辑清晰
⚠️ 缺点：递归深度过大时可能导致栈溢出

3.2 迭代法

✅ 使用队列实现迭代翻转，适用于树结构较大的场景。

思路是：使用一个队列保存待处理的节点，每次从队列中取出一个节点，交换其左右子节点，然后将其子节点加入队列继续处理。

public void reverseIterative(TreeNode treeNode) {
    List<TreeNode> queue = new LinkedList<>();

    if (treeNode != null) {
        queue.add(treeNode);
    }

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

        // 先保存子节点，再交换
        if (node.getLeftChild() != null) {
            queue.add(node.getLeftChild());
        }
        if (node.getRightChild() != null) {
            queue.add(node.getRightChild());
        }

        // 交换左右子节点
        TreeNode temp = node.getLeftChild();
        node.setLeftChild(node.getRightChild());
        node.setRightChild(temp);
    }
}

⚠️ 优点：避免递归栈溢出问题
⚠️ 缺点：代码稍复杂，需要维护队列

4. 小结

本文介绍了两种翻转二叉树的实现方式：

方法	是否递归	是否使用额外结构	适用场景
递归法	✅ 是	❌ 否	简单、结构清晰
迭代法	❌ 否	✅ 是（队列）	避免栈溢出，适合大树

✅ 两种方法都可在 O(n) 时间内完成整棵树的翻转，n 为节点总数。空间复杂度分别为 O(h)（递归）和 O(n)（迭代）。

完整代码和测试用例可以参考：GitHub 仓库

Persistence

REST

Security