[剑指Offer] 28_对称二叉树

题目

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么他是对称的。

例：

---

思路

1. 生成一棵镜像树，再逐一比对。
   1. 时间复杂度：O(n)，但是慢于下面两种，因为要遍历2次。
   2. 空间复杂度：O(n)
2. 递归比较，双指针，一个按父-左-右遍历，一个按父-右-左遍历，每一步都比较两者是否相等。
   1. 时间复杂度：O(n)
   2. 空间复杂度：O(n)
3. 迭代比较，类似深度优先搜索，建立一个列表，每次弹出头第1、2个节点进行比较，按1左2右1右2左的顺序将下一次需要比较的节点存入队尾，直到列表清空或出现不等。
   1. 时间复杂度：O(n)
   2. 空间复杂度：O(n)

---

代码

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

def is_symmetrical(root):
    """
    :param root: root
    :return: bool
    """

    def re_core(preorder, symm_preoder):
        if not preorder and not symm_preoder:
            return True
        if not preorder or not symm_preoder:
            return False
        if preorder.val == symm_preoder.val:
            return re_core(preorder.left, symm_preoder.right) and re_core(preorder.right, symm_preoder.left)

    return re_core(root, root)

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

def isSymmetric(root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    layer = [root, root]
    while layer:
        left = layer.pop(0)
        right = layer.pop(0)
        if not left and not right:
            continue
        if not left or not right:
            return False
        if left.val == right.val:
            layer.extend([left.left, right.right, left.right, right.left])
        else:
            return False
    return True

---

思考

LeetCode 101. 对称二叉树