Day23 - 101.对称二叉树

题目链接：https://leetcode.cn/problems/symmetric-tree/description/

1. 问题理解

题目要求判断一棵二叉树是否轴对称，也就是这棵树是否以根节点为轴左右镜像相等。

直观理解：

• 树的左子树和右子树结构一样且对应节点的值相同，就算对称。

• 换句话说，如果把树沿着中间“折叠”，左边和右边能完全重合。

2. 核心算法

这里最直接的解法是递归比较：

• 定义一个函数 isMirror(t1, t2)，用于判断两个子树是否互为镜像。

• 规则：

  1. 如果 t1 和 t2 都是空，返回 True。

  2. 如果一个空一个不空，返回 False。

  3. 如果 t1.val == t2.val，继续递归比较：

     • t1.left vs t2.right

     • t1.right vs t2.left

整个过程就是同时检查左边的左子树和右边的右子树是否对称，以及左边的右子树和右边的左子树是否对称。

3. 关键点和边界条件

3.1 关键点

1. 对称条件：左树的左子节点 = 右树的右子节点，左树的右子节点 = 右树的左子节点。

2. 递归比较的是“镜像位置”，而不是普通的相等。

3. 根节点只需要检查它的左右子树是否互为镜像。

3.2 边界条件

• 空树：直接返回 True（空树本身是对称的）。

• root只有一个节点：也是对称的。

• 一个子树空另一个不空：立即返回 False。

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return None
        return self.compare(root.left,root.right)
        
    def compare(self,left,right):
        if left == None and right != None:
            return False
        elif left != None and right == None:
            return False
        elif left == None and right == None:
            return True
        elif left.val != right.val:
            return False 
        
        #开始递归该左右节点的左孩子和右孩子  后序遍历
        outside = self.compare(left.left,right.right)
        inside = self.compare(left.right,right.left)
        isSame = outside and inside

        return isSame