題目

  • 題目連結
  • 目標函式 : diameterOfBinaryTree(root)
    • Input : root: TreeNode
    • Output : int

解題概念

  • 題意 : 給定一 Binary tree 的 root，需要回傳該 tree 的直徑
  • Binary tree 直徑之定義 : 在 Binary tree 中，任意兩節點之間的最長路徑長
    • 該路徑可能會 or 不會經過 root

我的寫法

  • 想法 : 將直徑分成兩種狀況
    1. 該路徑有經過 root : 直接利用 maxDepth() 去計算左右子樹的最大深度並回傳
    2. 該路徑沒有經過 root : 需要找出該路徑中高度最高的節點，再利用 maxDepth() 去計算左右子樹的最大深度並回傳
  • 因此，需要對每個節點執行 maxDepth() 去確認 maxDepth，最後最大的 maxDepth 即為 tree 直徑
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    max_cnt = 0

    def diameterOfBinaryTree(self, root):
        
        def maxDepth(node):
            if not node: return 0

            left = maxDepth(node.left)
            right = maxDepth(node.right)

            # 更新 max_cnt
            self.max_cnt = max(self.max_cnt, left + right)

            # 繼續 maxDepth 之遞迴
            return max(left, right) + 1

        maxDepth(root)

        return self.max_cnt
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 28 ms (faster than 67.98%)
    • Memory Usage: 16.2 MB (more than 15.49%)

解答 or 其他優秀寫法

  • 想法 : 與我的寫法大致相同