python-leetcode 38.翻转二叉树

题目：

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

方法一：递归

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

互为镜像的条件：他们的两个根结点具有相同的值，每棵树的右子树都与另一个树的左子树镜像对称

可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，p指针和q指针一开始都指向这棵树的根，随后p右移时，q左移，p左移时，q右移。每次检查当前p和q节点的值是否相等，如果相等再判断左右子树是否对称。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        return self.check(root.left,root.right)
    def check(self,p,q):
        if p is None and q is None:
            return True 
        if p is None or q is None:
            return False
        return p.val==q.val and self.check(p.left,q.right) and self.check(p.right,q.left)

时间复杂度：O(n)

空间复杂度：O(n)

方法二：迭代

初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        return self.check(root,root) #同一个根节点是因为要比较树的左右子树
    def check(self,u,v):
        q=[]  #将节点 u 和 v（即左右子树的根节点）添加到队列中，接下来我们将对这些节点进行比较
        q.append(u)
        q.append(v)
        while q:
            u=q.pop(0)
            v=q.pop(0)#每次从队列中取出两个节点比较，看它们是否对称
            if u is None and v is None:#如果都是 None，说明这两个子树都为空，可以跳过这次比较
                continue
            if u is None or v is None or u.val !=v.val:
                return False
            q.append(u.left) #节点 u 和 v 的子节点按照对称的方式加入队列
            q.append(v.right)
            q.append(u.right)
            q.append(v.left)
        return True

时间复杂度：O(n)

空间复杂度：O(n)