LeetCode-101-对称二叉树

原题链接：https://leetcode-cn.com/problems/symmetric-tree/

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

image.png

解题思路：

1. 方法一：继承了层序遍历和回文字符串的判断，将每一层的数字（空叶子用-1表示）都存在tmp列表中，在判断tmp是否等于tmp[::-1]，等于就继续判断下一层；
2. 方法二：递归，用双指针p和q都指向root，递归地判断p和q的val相等，且判断p.left和q.right的val、p.right和q.left的val，以此类推；
3. 方法三：迭代，用队列存储偶数个节点，第一层存储root的左右叶子节点queue=[root.left, root.right]，此时遍历queue，每次取出两个节点，判断其val是否相等，并将这两个节点的叶子节点交叉加入queue，加入的顺序依次是left_node.left, right_node.right,left_node.right,left_node.left。

Python3代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        res = []
        queue = [root]

        while queue:
            size = len(queue)
            tmp = []
            for i in range(size):
                node = queue.pop(0)
                if node == -1:
                    tmp.append(-1)
                else:
                    tmp.append(node.val)
                if node != -1:
                    if node.left:
                        queue.append(node.left)
                    else :
                        queue.append(-1)
                if node != -1:
                    if node.right:
                        queue.append(node.right)
                    else:
                        queue.append(-1)
            if tmp != tmp[::-1]:
                return False
        return True

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # 递归
        def check(p, q):
            if not p and not q: return True
            if not p or not q: return False
            return p.val == q.val and check(p.left, q.right) and check(p.right, q.left)

        if not root:
            return True
        return check(root.left, root.right)

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # 迭代
        # root空 或者 root没有左右子树
        if not root or not (root.left or root.right):
            return True
        queue = [root.left, root.right]
        while queue:
            u = queue.pop(0)
            v = queue.pop(0)
            # u 和 v 都为空
            if not (u or v): 
                continue
            # u 和 v 其中之一为空
            if not (u and v): 
                return False
            if u.val!=v.val:
                return False
            queue.append(u.left)
            queue.append(v.right)
            queue.append(u.right)
            queue.append(v.left)
        return True