更多題目移步【力扣簡單題】

題目

難度：★☆☆☆☆
類型：二叉樹

給定一個二叉樹，檢查它是否是鏡像對稱的。

示例

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

說明:

如果你可以運(yùn)用遞歸和迭代兩種方法解決這個問題，會很加分。

解答

這道題和【100.相同的樹】很類似，我們可以使用遞歸和隊(duì)列兩種方式實(shí)現(xiàn)。

方案1：遞歸

對稱的樹的左子樹和右子樹滿足以下條件：

1. 如果左子樹或右子樹均為空，則該樹對稱；

2. 如果左子樹或右子樹只有一個為空，則該樹不對稱；

3. 如果左子樹和右子樹均不為空，當(dāng)左子樹的左子樹和右子樹的右子樹鏡像對稱，且左子樹的右子樹和右子樹的左子樹鏡像對稱時(shí)，該樹對稱。

class Solution:
    def isSymmetric(self, root):
        """
        遞歸
        :param root:
        :return:
        """
        def is_mirror(p, q):         # 判斷左右子樹是否鏡像對稱
            if not p and not q:
                return True
            elif not p and q or p and not q:
                return False
            else:
                return p.val == q.val and is_mirror(p.left, q.right) and is_mirror(p.right, q.left)

        return is_mirror(root, root)

方案2：隊(duì)列

1. 對根節(jié)點(diǎn)進(jìn)行非空判斷，將根節(jié)點(diǎn)的左右子樹放在一個隊(duì)列中；

2. 每次成對取出節(jié)點(diǎn)，這兩個節(jié)點(diǎn)其實(shí)是二叉樹的對稱位置，判斷這兩個節(jié)點(diǎn)的相等情況：
   （1）如果兩結(jié)點(diǎn)均為空，則繼續(xù)下一輪循環(huán)；
   （2）如果兩結(jié)點(diǎn)只有一個是空，直接返回Fasle；
   （3）如果兩結(jié)點(diǎn)都不為空，且它們的數(shù)值不同，也直接返回False；
   （4）此時(shí)兩結(jié)點(diǎn)的數(shù)值一定相等，將它們的左右子結(jié)點(diǎn)逆序加入到隊(duì)列中，保證每一對結(jié)點(diǎn)都是對稱的位置。

3. 如果到最后，隊(duì)列中為空，則二叉樹對稱，返回True。

class Solution:
    def isSymmetric(self, root):
        """
        隊(duì)列
        :param root:
        :return:
        """

        if not root:
            return True

        node_queue = [root.left, root.right]    # 在空隊(duì)列中加入左子樹和右子樹

        while node_queue:
            left = node_queue.pop(0)            # 依次彈出兩個元素
            right = node_queue.pop(0)

            if not right and not left:          # 如果均為空，繼續(xù)下一個循環(huán)
                continue
            if not right or not left:           # 如果只有一個為空，返回False
                return False

            if left.val != right.val:           # 都非空，再判斷值是否相等
                return False

            node_queue.append(left.left)        # 將兩個左右子樹的左右子樹逆序加入隊(duì)列
            node_queue.append(right.right)
            node_queue.append(left.right)
            node_queue.append(right.left)

        return True

如有疑問或建議，歡迎評論區(qū)留言~