樹-101鏡像樹-簡單-20210813python

樹-101鏡像樹-簡單-20210813

1. 題目描述

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

示例：

例如，二叉樹

[1,2,2,3,4,4,3]

是對稱的。

1
   / \
  2   2
 / \ / \
3  4 4  3

         1
      /     \
    2         2
   / \       / \
  3   4     4   3
 / \ / \   / \ / \
8  7 6  5 5  6 7  8

           

但是下面這個

[1,2,2,null,3,null,3]

則不是鏡像對稱的:

1
   / \
  2   2
   \   \
   3    3
           

你可以運用遞歸和疊代兩種方法解決這個問題嗎？

2. 題目解答

2.1 遞歸-深度搜尋

滿足條件：

• 它們的兩個根結點具有相同的值【比較

  left

  的左節點和

  right

  的右節點，再比較

  left

  的右節點和

  right

  的左節點】
• 每個樹的右子樹都與另一個樹的左子樹鏡像對稱【将根節點的左子樹記做

  left

  ，右子樹記做

  right

  。比較

  left

  是否等于

  right

  】

終止條件：

• 左右都為空，True
• 其中一個為空，False
• 左右不相等，False

時間複雜度：O(n)，因為要周遊 n個節點

空間複雜度：O(n)，空間複雜度是遞歸的深度，也就是跟樹高度有關，最壞情況下樹變成一個連結清單結構，高度是n

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        def dfs(left, right):
            if not left and not right:
                return True  # not (left or right)
            if not left or not right:
                return False  # not (left and right)
            if left.val != right.val:
                return False
            return dfs(left.left, right.right) and dfs(left.right, right.left)
        return dfs(root.left, root.right)
           

2.2 疊代-廣度搜尋

初始化時我們把根節點入棧/隊列兩次。每次提取兩個結點并比較它們的值（棧/隊列中每兩個連續的結點應該是相等的，而且它們的子樹互為鏡像），然後将兩個結點的左右子結點按相反的順序插入棧/隊列中。當棧/隊列為空時，或者我們檢測到樹不對稱（即從棧/隊列中取出兩個不相等的連續結點）時，該算法結束

class Solution:
    # 棧疊代方法，如果是隊列使用pop(0)
    def is_symmetric1(self, root):
        stack = [root, root]
        while stack:
            left = stack.pop()
            right = stack.pop()
            if left is None and right is None:
                continue
            if left is None or right is None or left.val != right.val:
                return False
            stack.append(left.left)
            stack.append(right.right)
            stack.append(left.right)
            stack.append(right.left)
        return True
    def is_symmetric2(self, root):
        if not root: return True
        stack = [(root.left, root.right)]
        while stack:
            left, right = stack.pop()
            if left is None and right is None:
                continue
            if left and right and left.val == right.val:
                stack.append((left.left, right.right))
                stack.append((left.right, right.left))
            else: return False
        return True
    
    
    # 利用層次搜尋方法
    def is_symmetric_BFS(self, root):
        if not root: return True
        if not (root.left or root.right): return True

        stack = [root]
        while stack:
            n = len(stack)
            vals = []  #  存放每層的值
            for i in range(n):
                s = stack.pop(0)
                if s:
                    vals.append(s.val)
                    stack.append(s.left)
                    stack.append(s.right)
                else: vals.append('null')
            i = 0
            while i < (len(vals) // 2):
                if vals[i] != vals[-1-i]: return False
                i += 1
        return True
           

3. 測試用例

1. 功能測試:
    對稱[1,2,2,3,4,4,3]
    不對稱[1,2,2,'null',3,'null',3]
2. 特殊測試：
	隻有一個值[2]
     空[]