101.对称二叉树

题目:101.对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

• 示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

• 示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

• 提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

思路

要检查一个二叉树是否是轴对称的（即镜像对称），可以通过递归的方法来解决。具体来说，我们需要判断二叉树的左子树和右子树是否是镜像对称的。

1. 如果根节点为空，树是对称的，直接返回 true。
2. 定义一个递归函数 isMirror(left, right) 来判断左子树和右子树是否是镜像对称的：
   • 如果两个节点都为空，返回 true。
   • 如果其中一个节点为空而另一个节点不为空，返回 false。
   • 如果两个节点的值不相等，返回 false。
   • 递归判断 left 的左子树和 right 的右子树，以及 left 的右子树和 right 的左子树是否对称。
3. 使用 isMirror 函数来判断根节点的左子树和右子树是否对称。

• 时间复杂度:O(n)，其中 n 是二叉树的节点数
• 空间复杂度:O(h)，其中 h 是二叉树的高度

代码

public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    // 调用辅助函数判断左右子树是否镜像对称
    return isMirror(root.left, root.right);
}

// 辅助函数：判断两个子树是否镜像对称
private boolean isMirror(TreeNode leftNode, TreeNode rightNode) {
    // 如果两个子树都为空，返回 true
    if (leftNode == null && rightNode == null) {
        return true;
    } else if (leftNode == null || rightNode == null) {
        // 如果其中一个子树为空，另一个不为空，返回 false
        return false;
    } else if (leftNode.val != rightNode.val) {
        // 如果两个子树的当前节点值不同，返回 false
        return false;
    }
    // 递归判断子节点
    return isMirror(leftNode.left, rightNode.right) && isMirror(leftNode.right, rightNode.left);
}