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

題目

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

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

示例

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

說明:

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

解答

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

方案1：遞歸

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

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

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

3. 如果左子樹和右子樹均不為空，當左子樹的左子樹和右子樹的右子樹鏡像對稱，且左子樹的右子樹和右子樹的左子樹鏡像對稱時，該樹對稱。

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：隊列

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

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

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

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

        if not root:
            return True

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

        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)        # 將兩個左右子樹的左右子樹逆序加入隊列
            node_queue.append(right.right)
            node_queue.append(left.right)
            node_queue.append(right.left)

        return True

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