每日一道算法题：判断对称二叉树

题目描述

给定一棵二叉树，判断是否是对称二叉树。

解题思路

定义对称二叉树

对称二叉树是指一个二叉树的左右两个子树镜像对称。

递归解法

从根节点开始，判断左右子树是否对称，判断方法是比较左右子树的根节点值是否相等，然后分别递归判断左子树的左子树和右子树的右子树是否对称，左子树的右子树和右子树的左子树是否对称。

非递归解法

使用队列辅助遍历二叉树，每次将左右节点按照对称的方式加入队列中，再逐个比较是否对称。

代码实现

递归解法代码

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

private boolean isSymmetric(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }
    if (left == null || right == null || left.val != right.val) {
        return false;
    }
    return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}

非递归解法代码

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;
        }
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        queue.offer(left.left);
        queue.offer(right.right);
        queue.offer(left.right);
        queue.offer(right.left);
    }
    return true;
}

时间复杂度

递归解法的时间复杂度为O(n)，非递归解法的时间复杂度为O(n)，其中n为树的节点数。

空间复杂度

递归解法的空间复杂度为O(n)，非递归解法的空间复杂度为O(n)，其中n为树的节点数。

边界条件处理

当树为空时，判断为对称二叉树。

测试用例

输入：

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

输出：true

输入：

    1
   / \
  2   2
   \   \
   3    3

输出：false

扩展点

对称二叉树图像的翻转

对于一棵对称二叉树，将其左右子树交换位置后得到的二叉树与原二叉树是镜像对称的。

对称二叉树的遍历

前序遍历：根-左-右，左右子树按照对称顺序遍历

中序遍历：左-根-右，左右子树按照对称顺序遍历

后序遍历：左-右-根，左右子树按照对称顺序遍历

总结

总结解题思路

本题可以使用递归和非递归两种方式解决。递归方式就是比较左右子树是否对称，如果对称则继续递归比较左子树的左子树和右子树的右子树，左子树的右子树和右子树的左子树是否对称。非递归方式需要使用队列辅助，每次将左右节点按照对称的方式加入队列中，再逐个比较是否对称。

总结时间复杂度和空间复杂度

递归解法和非递归解法的时间复杂度和空间复杂度都是O(n)，其中n为树的节点数。

总结对称二叉树的应用场景

对称二叉树是一种常见数据结构，其应用场景可以是二叉树镜像的问题，判断两棵树是否相同的问题等等。在算法中也有一些与对称二叉树相关的问题，例如二叉树的最大深度、路径总和等。