力扣101. 对称二叉树（递归法，迭代法，层次遍历法）

本文介绍: 给你一个二叉树的根节点 root，检查它是否轴对称。true false。

题目：

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

示例 1：

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

示例 2：

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

代码及详细 注释：

递归法：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -&gt; bool:
        if not root:
            return True  # 如果根结点为空，返回True（空树被认为是对称的）
        return self.compare(root.left, root.right)  # 调用compare函数比较左右子树是否对称

    def compare(self, left, right):
        if left == None and right == None:  # 如果左右子结点都为空，返回True
            return True
        elif left != None and right == None:  # 如果左子结点不为空，右子结点为空，返回False
            return False
        elif left == None and right != None:  # 如果左子结点为空，右子结点不为空，返回False
            return False
        elif left.val != right.val:  # 如果左右子结点的值不相等，返回False
            return False
        outside = self.compare(left.left, right.right)  # 比较左子结点的左子树和右子结点的右子树是否对称
        inside = self.compare(left.right, right.left)  # 比较左子结点的右子树和右子结点的左子树是否对称
        result = outside and inside  # 如果两个子树都对称，返回True，否则返回False
        return result

迭代法：（栈和队列都可以，代码思路相同，略微改动部分，本题用的栈）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True  # 如果根结点为空，返回True（空树被认为是对称的）
        stack = []  # 创建一个栈，用于存储左右子结点
        stack.append(root.left)  # 将左子结点加入栈
        stack.append(root.right)  # 将右子结点加入栈
        while stack:  # 当栈不为空时循环
            rightNode = stack.pop()  # 从栈中取出右子结点
            leftNode = stack.pop()  # 从栈中取出左子结点
            if not leftNode and not rightNode:  # 如果左右子结点都为空，继续下一次循环
                continue
            elif not leftNode or not rightNode or leftNode.val != rightNode.val:  # 如果左右子结点有一个为空，或者它们的值不相等，返回False
                return False
            stack.append(leftNode.left)  # 将左子结点的左子结点加入栈
            stack.append(rightNode.right)  # 将右子结点的右子结点加入栈
            stack.append(leftNode.right)  # 将左子结点的右子结点加入栈
            stack.append(rightNode.left)  # 将右子结点的左子结点加入栈
        return True  # 如果所有结点都对称，返回True

层次遍历：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True  # 如果根结点为空，返回True（空树被认为是对称的）
        
        from collections import deque
        queue = deque([root.left, root.right])  # 创建一个双端队列，用于存储左右子结点
        while queue:  # 当队列不为空时循环
            size = len(queue)  # 获取当前队列的长度
            if size % 2 != 0:  # 如果当前队列长度为奇数，说明不对称，返回False
                return False
            level = []  # 创建一个空列表，用于存储当前层的结点值
            for i in range(size):
                node = queue.popleft()  # 从队列中取出一个结点
                if node:  # 如果结点不为空
                    level.append(node.val)  # 将结点值加入当前层列表
                    queue.append(node.left)  # 将左子结点加入队列
                    queue.append(node.right)  # 将右子结点加入队列
                else:  # 如果结点为空
                    level.append(None)  # 将None加入当前层列表
            if level != level[::-1]:  # 如果当前层列表不等于它的逆序列表，说明不对称，返回False
                return False
        return True  # 如果所有层都对称，返回True