📃 题目描述

题目链接：

• 剑指 Offer 28. 对称的二叉树 (opens new window)
• 101. 对称二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

🔔 解题思路

递归

递归三部曲

1. 确定递归函数的参数和返回值

因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的其实就是根节点的两个子树，参数自然也是左子树节点和右子树节点。返回值自然是 boolean 类型。

代码如下：

bool compare(TreeNode* left, TreeNode* right)

2. 确定终止条件

要比较两个节点(两棵树的根节点)数值相不相同（如果两棵树的根节点都不一样，那这两棵树一定不是对称的），首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。

节点为空的情况有：

• 左右都为空，对称，返回true
• 左节点为空，右节点不为空，或者左不为空，右为空，不对称，return false

此时已经排除掉了节点为空的情况，那么剩下的就是左右节点都不为空的情况：

• 左右都不为空，比较节点数值，不相同就 return false

此时左右节点不为空，且数值也不相同的情况我们也处理了。

最后，剩下的就是 left == right 的情况，可以开始判断这两棵子树是否对称了

3. 确定单层递归的逻辑

此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。

• 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
• 比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
• 如果左右都对称就返回 true ，有一侧不对称就返回 false

如上代码中，我们可以看出使用的遍历方式，左子树左右中，右子树右左中，所以我把这个遍历顺序也称之为 “后序遍历”（尽管不是严格的后序遍历）。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return compare(root.left, root.right);
    }

    /**
     * 判断 left 和 right 是否对称
     * @param left root 左子树的根节点
     * @param right root 右子树的根节点
     * @return
     */
    private boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        // 剩下的就是 left 和 right 都不为 null 或者有一个为 null 的情况
        else if (left == null || right == null) {
            return false;
        }
        // 剩下的就是 left 和 right 都不为 null 的情况
        else if (left.val != right.val) {
            return false;
        }

        // 剩下的就是 left == right 的情况，可以开始判断这两棵子树是否对称了
        // 1. 外侧节点(左子树的左节点，右子树的右节点)
        boolean outside = compare(left.left, right.right);
        // 2. 内侧节点(左子树的右节点，右子树的左节点)
        boolean inside = compare(left.right, right.left);

        return outside && inside;
    }
}

迭代

这一题迭代的思路其实也很简单，通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等，成对地将左右子树中要比较的元素顺序放进一个队列中，如果相同则表示对称

代码如下：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

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

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

            if (left == null && right == null) {
                // 注意这是 continue 而不是 return true
                continue;
            }
            // 剩下的就是 left 和 right 都不为 null 或者有一个为 null 的情况
            else if (left == null || right == null) {
                return false;
            }
            // 剩下的就是 left 和 right 都不为 null 的情况
            else if (left.val != right.val) {
                return false;
            }
            // 剩下的就是 left == right 的情况，直接入队进入下一轮处理
            // 外侧节点成对入队
            queue.offer(left.left);
            queue.offer(right.right);
            // 内侧节点成对入队
            queue.offer(left.right);
            queue.offer(right.left);
        }

        return true;
    }

}

💥 复杂度分析

• 空间复杂度：递归和迭代法的空间复杂度都是 O(LogN)，因为递归底层其实调用了栈空间
• 时间复杂度：递归和迭代法的时间复杂度相同，每个节点仅会被处理到两次，总的时间复杂度为 O(N)