力扣-第101题--对称二叉树(python)--详细解析--逐步调试

原题：

链接：https://leetcode-cn.com/problems/symmetric-tree/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-er-ch-hnjo/

递归法：
解题思路：
1、首先判断根目录是否为空节点，如果是，返回True；

if not root:
    return True

2、如果不符合1中的条件，说明存在根节点，就直接返回return后面的；

return self.compare(root.left, root.right)

3、执行compare()方法，将 root.left 传递给 left，将 root.right 传递给 right。
4、这里compare()方法，首先排序空节点的情况，着重考虑以下四种情况：

• 如果root.left为空，root.right 不为空，则说明不对称，为False；

if left == None and right != None: return False

• 如果root.left不为空，root.right为空，则说明不对称，为False；

elif left != None and right == None: return False

• 如果root.left为空，root.right为空，则说明是对称的，为True；

elif left == None and right == None: return True

• 如果root.left节点值不等于root.right节点值，则也不是对称的，为False。

elif left.val != right.val: return False

5、检查是否有空节点后，此时才做递归，做下一层的判断。
在上一层 root.left 和 root.right 的基础上，在下一层中：执行compare()方法，将 left.left 传递给 left，将 right.right 传递给 right…
如下图所示，逐一的检查，只要有其中一个不满足条件，就False；

outside = self.compare(left.left, right.right) #左子树：左、 右子树：右
inside = self.compare(left.right, right.left) #左子树：右、 右子树：左

6、最后，outside 和 inside 要么是True ，要么是False，所以最后判断以根节点root的左右子树是否相同，不同就False。

isSame = outside and inside #左子树：中、 右子树：中 （逻辑处理）

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        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