【leetcode100】对称二叉树

1、题目描述

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

示例 1：

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

2、初始思路

2.1 思路

利用翻转的原理进行对比，从而判断是否对称。

# 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:
        def symmetric(node):
            if node == None:
                return 
            symmetric(node.left)
            symmetric(node.right)
            node.left, node.right = node.right, node.left
        root_ori = root
        symmetric(root)
        if root == root_ori:
            return True
        else:
            return False

2.2 犯错点

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

对上述判断出现错误，上图二叉树反转后与原二叉树相同，但显然其不满足对称二叉树的条件。

3 正确算法

3.1 思路

利用镜像的原理，以此判断左子树的左子树与右子树的右子树、左子树的右子树与右子树的左子树是否一致。

# 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:
        def isMirror(left, right):
            if left == None and right == None:
                return True
            if left == None or right == None:
                return False
            return (left.val == right.val) and isMirror(left.left, right.right) and isMirror(left.right, right.left)
        if not root:
            return True
        return isMirror(root.left, root.right)