Python程式：查詢葉節點列表中最小樹的總和

假設我們有一個名為nums的數字列表。此列表表示樹的中序遍歷中的葉節點。這裡，內部節點有兩個子節點，其值與其左子樹的最大葉節點值和右子樹的最大葉節點值的乘積相同。我們必須找到具有最小值總和的樹的總和。

因此，如果輸入類似於nums = [3, 5, 10]，則輸出將為83。

為了解決這個問題，我們將遵循以下步驟

  • res := nums中所有元素的總和
  • 當nums的大小> 1時，執行以下操作
    • i := nums的最小元素的索引
    • 當i> 0時，left := nums[i - 1]，否則為無窮大
    • 當i< nums的大小 - 1時，right := nums[i + 1]，否則為無窮大
    • res := res + (left和right的最小值) * nums的第i個元素，然後從nums中刪除第i個元素
  • 返回res

讓我們檢視以下實現以更好地理解

示例程式碼

線上演示

class Solution:
   def solve(self, nums):
      res = sum(nums)
      while len(nums) > 1:
         i = nums.index(min(nums))
         left = nums[i - 1] if i > 0 else float("inf")
         right = nums[i + 1] if i < len(nums) - 1 else float("inf")
         res += min(left, right) * nums.pop(i)

      return res

ob = Solution()
nums = [3, 5, 10]
print(ob.solve(nums))

輸入

[3, 5, 10]

輸出

83

更新於: 2020年11月25日

158 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告