22对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [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

image.png

首先我们对这棵树根节点的左子树进行前序遍历: pre_order = [2,3,5,6,4,7,8]
接着我们对这棵树根节点的右子树进行后序遍历：post_order =[8,7,4,6,5,3,2]
根据两次遍历我们不难发现 post_order 就是 pre_order的逆序，其实这也是对称二叉树的一个性质

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        bli = []     # 用来存左子树的前序遍历
        fli = []     # 用来存右子树的后序遍历
        if root == None:   # 无根节点
            return True
        if root and root.left == None and root.right == None:  # 只有根节点
            return True

        if root and root.left and root.right:
            self.pre_order(root.left, bli)
            self.post_order(root.right, fli)
            fli.reverse()            # 将后序遍历的列表倒序
            if bli == fli:
                return True
            else:
                return False

    def pre_order(self,root,li):    # 二叉树的前序遍历
        if root:
            li.append(root.val)
            self.pre_order(root.left,li)
            self.pre_order(root.right,li)
        elif root == None:
            li.append(None)

    def post_order(self,root,li):   # 二叉树的后序遍历
        if root:
            self.post_order(root.left,li)
            self.post_order(root.right,li)
            li.append(root.val)
        elif root == None:
            li.append(None)

递归

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def help(left, right):
        # left/right都为空节点
            if not left and not right:
                return True
        # left/right有一个为空
            if not (left and right):
                return False
        # 值是否相等
            if left.val != right.val:
                return False
        # 将左右字节对称递归比较
            return help(left.left, right.right) and help(left.right, right.left)
   
        return help(root.left, root.right) if root else True

迭代

from collections import deque

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        deq = deque([root, root])
        while deq:
            t1, t2 = deq.pop(), deq.pop()
        # 两个节点都为空, 则继续判断
            if not t1 and not t2: continue
        # 存在一个节点为空, 则为False
            if not(t1 and t2): return False
            if t1.val != t2.val: return False
        # t1, t2的左右节点, 要对称的写入双端队列中
            deq.append(t1.left)
            deq.append(t2.right)
            deq.append(t1.right)
            deq.append(t2.left)
        
        return True

BFS
BFS 使用一个队列，很多题解中的 BFS 都是放入了四次节点，一种更直观的做法是两两一组放入队列中。
在队列中同时取出两个节点left, right，判断这两个节点的值是否相等，然后把他们的孩子中按照(left.left, right.right) 一组，(left.right, right.left)一组放入队列中。
BFS做法需要把所有的节点都检查完才能确定返回结果True，除非提前遇到不同的节点值而终止返回False。

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        queue = collections.deque()
        queue.append((root, root))
        while queue:
            left, right = queue.popleft()
            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.val != right.val:
                return False
            queue.append((left.left, right.right))
            queue.append((left.right, right.left))
        return True

来源：力扣（LeetCode）