101. 对称二叉树

Difficulty
easy
Tags
二叉树
URL
https://leetcode-cn.com/problems/symmetric-tree/
Star
❤
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    1
   / \
  2   2
   \   \
   3    3
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？

法1 递归法

思路
采用递归 遍历，一个 左右中 一个 右左中 遍历，来判断是否一样
题解
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return self.isMirror(root.left, root.right)
    def isMirror(self, left, right):
        if left == None and right == None:
            return True
        if left == None or right == None:
            return False
        return left.val == right.val and \
								self.isMirror(left.left, right.right) and \
								self.isMirror(left.right, right.left)

法2 队列

思路
类似层次遍历，将每个节点存到队列中，然后逐个判断
存到队列的时候，按照 外层 内层 or 内层 外层 的顺序存 。此处存到队列的不只是非空节点，如果遇到空节点也是要存进去的
题解
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root is None:
            return True
        queue = []
        queue.append(root.left)
        queue.append(root.right)
        while len(queue) > 0:
            # 先判断一下，队列里面节点是否为2的倍数，如果不是那肯定不是对称
            if len(queue) % 2 != 0:
                return False
            leftNode = queue.pop(0)
            rightNode = queue.pop(0)
            # 左右节点均为空
            if leftNode is None and rightNode is None:
                continue
            # 左右存在一个不为空 or 左右值不相同
            elif leftNode is None or rightNode is None:
                return False
            # 左右均不为空
            elif leftNode.val != rightNode.val:
                return False
   
            # 将外层节点放到队列
            queue.append(leftNode.left)
            queue.append(rightNode.right)
            # 将内层节点放到队列
            queue.append(leftNode.right)
            queue.append(rightNode.left)
            
        return True