題目

  • 題目連結
  • 目標函式 : levelOrder(root)
    • Input : root: TreeNode
    • Output : List[List[int]]

解題概念

  • 題意 : 給定一 Binary Tree 的樹根 root，需要回傳該樹所有 node 之 value 的 Level Order Traversal

我的寫法

  • 想法 : 這題也是 Binary Tree 題型中很經典的一題，而這題會使用 BFS 去處理
    • 不過比一般 BFS 不同的地方在於，它需要將每一層的 value 都打包進一 list 中，最後彙整完再回傳
    • 因此需要以下變數 :
      • res : 儲存最後回傳之結果
      • queue : 當作 Queue 使用
      • each_round : 紀錄每一層所有的 TreeNode
      • each_val : 紀錄每一層所有的 value
  • 程式碼 : 
    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
    def levelOrder(self, root):
        
        res = []
        queue = []
        if root != None:
            queue.append(root) # 先將 root 丟進 Queue 中
        each_round = []
        each_val = []

        while len(queue) != 0:
            
            node = queue.pop(0) # 對 Queue 進行 dequeue()
            each_val.append(node.val) # 將該節點的 value 加到 each_val

            if node.left != None: # 若左子點不為空
                each_round.append(node.left) # 則將左子點加到 each_round
            if node.right != None: # 若右子點不為空
                each_round.append(node.right) # 則將右子點加到 each_round

            if len(queue) == 0: # 若發現 Queue 為空，代表此時該層所有的節點都已瀏覽過
                res.append(each_val) # 將 each_val 整個加到 res 中
                each_val = [] # 重整 each_val

                queue += each_round # 將 each_round 中的節點全部丟到 Queue 中
                each_round = [] # 重整 each_round

        return res
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 19 ms (faster than 81.78%)
    • Memory Usage: 14 MB (more than 88.24%)

解答 or 其他優秀寫法

  • 想法 : 把 each_round 變數拿掉，改使用 for 迴圈去處理每一層
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    def levelOrder(self, root):
        
        res = []
        queue = []

        if root == None: return res

        queue.append(root)

        while len(queue) != 0:
            each_val = []
            for i in range(len(queue)):
                node = queue.pop(0)
                each_val.append(node.val)
                if node.left != None:
                    queue.append(node.left)
                if node.right != None:
                    queue.append(node.right)

            res.append(each_val)

        return res
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 18 ms (faster than 84.73%)
    • Memory Usage: 14.15 MB (more than 57.54%)