二叉树 | 递归法 101.对称二叉树

leetcode 101.对称二叉树

题目

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

解题思路

递归法，判断左节点的左孩子是否可以翻转成右节点的右孩子（左节点的左孩子 == 右节点的右孩子，左节点的右孩子 == 右节点的左孩子）
递归三步骤：
1、确定递归函数的入参和返回值 入参：左节点、右节点 返回值：bool值
2、递归的终止条件
（1）左节点为空，右节点为空 返回True
（2）左节点为空，右节点不为空 返回False
（3）左节点不为空，右节点为空 返回False
（4）左节点不为空，右节点不为空，左节点 != 右节点 返回False
3、单层遍历的条件和逻辑（递归的具体逻辑）：左节点不为空，右节点不为空，左节点 == 右节点
判断左节点是否可以翻转成右节点
（1）外侧节点比较 左节点的左孩子 == 右节点的右孩子
（2）内侧节点比较 左节点的右孩子 == 右节点的左孩子
（3）外侧节点比较结果一样，且内侧节点比较结果一样 -> 左节点可以翻转成右节点

实现代码

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:
        return self.compare(root.left, root.right)

    def compare(self, left, right):
        if not left and not right:  # 左节点右右节点都为空，只有根节点，返回True
            return True
        elif left and not right:    # 左节点不为空，右节点为空，返回False
            return False
        elif right and not left:    # 左节为空，右节点不为空，返回Fasle
            return False
        elif left.val != right.val: # 左节点和右节点都不为空，但左节点的的值不等于右节点的值，返回False
            return False
            
        outside = self.compare(left.left, right.right)  # 外侧：比较左节点的左孩子和右节点的右孩子
        inside = self.compare(left.right, right.left)   # 内侧：比较左节点的右孩子和右节点的左孩子
        isSameValue = outside and inside    # 外侧和内侧的值都为True,则返回True
        return isSameValue