101_对称二叉树

类型：树

对称二叉树 💚 ⭐

https://leetcode-cn.com/problems/symmetric-tree/

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

💡 递归

如果一棵树的左右子树互为镜像对称，那么这棵树是对称的。

两棵树在什么情况下满足互为镜像对称？

它们的根结点值相同
A 树的左子树与 B 树的右子树镜像对称
A 树的右子树与 B 树的左子树镜像对称

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

    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        return self.check(root.left, root.right)

时间复杂度：O(n)，空间复杂度：O(n)

💡 迭代

我们引入队列来将递归改写成迭代。

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

class Solution:    
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True

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

时间复杂度：O(n)。空间复杂度：O(n)，队列长度不会超过 n