【代码随想录day15】对称二叉树

题目 

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

示例 1：

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

思路

这个分类成简单题我是不认同的，递归逻辑虽然不复杂，但是第一次想也不好想出来的。

递归解法 

对于两个节点是否相等，有5种可能的情况：

1. 左空右不空：False
2. 左不空右空：False
3. 左空右空：True
4. 左不空右不空且值不相等：False
5. 左不空右不空且值相等：继续递归判断 左节点的左子树和右节点的右子树 和 左节点的右子树和右节点的左子树 是否相等。当两个都相等时，返回True，否则返回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]) -> bool:
        def isSame(left,right):
            if left and not right:   
                return False
            elif not left and right: 
                return False
            elif not left and not right: 
                return True
            elif left and right and left.val!=right.val: 
                return False
            outside = isSame(left.left,right.right)
            inside = isSame(left.right,right.left)
            return inside and outside
        if not root:
            return True
        return isSame(root.left,root.right)

迭代解法 

其实这个用栈和队列都可以，整个过程和括号匹配有点像，思路是用容器同时存储两个“本该配对的节点”，然后在迭代的过程中不断的从容器中弹出一对节点，判断它俩是否相同，如果是则继续迭代直到把所有节点全部迭代完返回True，如果中间有不匹配的则直接返回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]) -> bool:
        if not root:
            return True
        stack = [root.right,root.left]
        while stack:
            left = stack.pop()
            right = stack.pop()
            if not left and not right:
                continue
            if not left or not right or left.val!=right.val:
                return False
            
            stack.append(left.right)
            stack.append(right.left)
            stack.append(left.left)
            stack.append(right.right)
        return True