連結

101. Symmetric Tree
https://leetcode.com/problems/symmetric-tree/

這是我一開始的想法，乍看下這樣的方式執行下來是可行的，但題目給的類別並不是一個 list 而是 TreeNode

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def isSymmetric(self, root):
        # 依據 1、2、4、8..... 為一組的方式分組並檢查每個裡面是否對稱
        root_len = len(root)
        j = 2
        for i in range(root_len):
            check_list = root[j-1:j*2-1]
            if check_list != check_list[::-1]:
                return False
            j = j*2
            if j*2-1 > root_len:
                break
        return True

有趣的是，我偷吃步直接使用 treeToList() 把 TreeNode 轉成 list 並且處理，這方式確實是可行的，但不會是最佳解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def isSymmetric(self, root):
        # 先使用另個函式把 TreeNode 轉成 list
        root = self.treeToList(root)
        # 再使用原本(上述)的方式處理
        root_len = len(root)
        j = 2
        for i in range(root_len):
            check_list = root[j-1:j*2-1]
            if check_list != check_list[::-1]:
                return False
            j = j*2
            if j*2-1 > root_len:
                break
        return True

    def treeToList(self,root):
        if not root:
            return []
        result = [root.val]
        left = self.treeToList(root.left)
        right = self.treeToList(root.right)
        for i in range(max(len(left), len(right))):
            if i < len(left):
                result.append(left[i])
            else:
                result.append(None)
            if i < len(right):
                result.append(right[i])
            else:
                result.append(None)
        return result

想法

1.可以用互補 ex:左右右==右左左
2.因為有要顧慮到兩邊，所以必須用兩個參數，一個左一個右
3.注意不能開新的對稱線，不能在子分支互相比較 ex:[4 | 3]=X [3,4 | 4,3]=V
4.請注意有無.val差別，一個是值一個是位置或None

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def isSymmetric(self, root):
        if root == None:
            return False
        return self.left_right(root.left, root.right)

    def left_right(self, left, right):
        if not left.left and not right.right:
            return True
        elif not left.left or not right.right:
            return False
        elif not left.right and not right.left:
            return True
        elif not left.right or not right.left:
            return False
        elif left.left.val != right.right.val:
            return False
        elif left.right.val != right.left.val:
            return False
        return self.left_right(left.left, right.right)

每次的修改都產生了不一樣的錯誤

  • 出現錯誤 ‘NoneType’ object has no attribute ‘val’
    Input：[1,0]
  • 只檢查了部分的子樹，5、null 沒被檢查到，就回傳 True 了
    Input：[2,3,3,4,5,null,4]
    Output：true
    Expected：false
    1
    2
    3
    4
    5
        2         
       / \
      3   3
     / \   \
    4   5   4
  • 在第三層的時候就已經提早回傳 True
    Input：[9,-42,-42,null,76,76,null,null,13,null,13]
    Output：true
    Expected：false
    1
    2
    3
    4
    5
    6
    7
        9       第一層
       / \
    -42  -42    第二層
      \   /
      76 76     第三層
     /   /
    13  13      第四層
  • 之後發現主要因為程式中有兩個錯誤才導致以上的問題
    1.呼叫時使用 left_right(left.left) 裡面又再次使用 left.left 會導致兩層，因此才會產生 NoneType 錯誤及提早結束的錯誤
    2.只呼叫 (left.left, right.right) 而 (left.right, right.left) 也是需要同時檢查的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def isSymmetric(self, root):
        # 之後發現其實 Leetcode 中沒有放特殊(空樹)的情形
        return self.left_right(root.left, root.right)

    def left_right(self, left, right):
        # 把 .left 及 .right 簡化過後，重複的條件是可以刪掉
        if not left and not right:
            return True
        elif not left or not right:
            return False
        elif left.val != right.val:
            return False
        # 使用 and 連接兩個不一樣方向的回傳值，表示只要有錯誤就一定回傳 False
        return self.left_right(left.left, right.right) and self.left_right(left.right, right.left)