Easy

题目描述

给你一个二叉树的根节点 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. 两个根节点的值相等
  2. 第一个树的左子树与第二个树的右子树互为镜像
  3. 第一个树的右子树与第二个树的左子树互为镜像

我们定义一个辅助函数 isMirror(left, right) 来判断两个子树是否互为镜像。

方法二：迭代

使用队列来模拟递归过程。每次从队列中取出两个节点进行比较，然后将它们的子节点按镜像顺序加入队列。

递归方法代码更简洁清晰，是首选解法。迭代方法虽然空间复杂度在最坏情况下相同，但避免了函数调用栈的开销。

代码实现

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isMirror(root, root);
    }
    
private:
    bool isMirror(TreeNode* left, TreeNode* right) {
        if (!left && !right) return true;
        if (!left || !right) return false;
        
        return left->val == right->val && 
               isMirror(left->left, right->right) && 
               isMirror(left->right, right->left);
    }
};

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def is_mirror(left, right):
            if not left and not right:
                return True
            if not left or not right:
                return False
            
            return (left.val == right.val and 
                    is_mirror(left.left, right.right) and 
                    is_mirror(left.right, right.left))
        
        return is_mirror(root, root)

public class Solution {
    public bool IsSymmetric(TreeNode root) {
        return IsMirror(root, root);
    }
    
    private bool IsMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        
        return left.val == right.val && 
               IsMirror(left.left, right.right) && 
               IsMirror(left.right, right.left);
    }
}

var isSymmetric = function(root) {
    if (!root) return true;
    
    function isMirror(left, right) {
        if (!left && !right) return true;
        if (!left || !right) return false;
        return left.val === right.val && 
               isMirror(left.left, right.right) && 
               isMirror(left.right, right.left);
    }
    
    return isMirror(root.left, root.right);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型递归方法迭代方法
时间复杂度O(n)O(n)
空间复杂度O(n)O(n)

其中 n 是二叉树的节点数。递归方法的空间复杂度主要来自递归调用栈，最坏情况下（完全不平衡树）为 O(n)，最好情况下（完全平衡树）为 O(log n)。迭代方法的空间复杂度来自队列存储。