leetcode-101

101. 对称二叉树

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

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

官方题解

递归

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

如果同时满足下面的条件，两个树互为镜像：

• 它们的两个根结点具有相同的值
• 每个树的右子树都与另一个树的左子树镜像对称

可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，p指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q 左移，p 左移时，q 右移。

每次检查当前 p和 q 节点的值是否相等，如果相等再判断左右子树是否对称。

class Solution:
    def check(self,p:TreeNode,q:TreeNode):
        if not p and not q:
            return True
        elif not p or not q:
            return False
        return  p.val == q.val and self.check(p.left,q.right) and self.check(p.right,q.left)
    def isSymmetric(self, root: TreeNode):
        return self.check(root,root)

迭代

首先我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。

初始化时我们把根节点入队两次。

每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。(兄弟节点都是诶着的)

当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续n结点）时，该算法结束。

class Solution:
    def check(self,root:TreeNode):
        queue = list()
        queue.append(root)
        queue.append(root)

        while queue:
            p = queue.pop(0)
            q = queue.pop(0)
            if not p and not q:
                continue
            elif not p or not q:
                return False
            if p.val != q.val:
                return False
            
            queue.append(p.left)
            queue.append(q.right)

            queue.append(p.right)
            queue.append(q.left)
        return True

    def isSymmetric(self, root: TreeNode):
        return self.check(root)