Pythonの葉のリストから最小の木の合計を見つけるプログラム

numsという番号のリストがあるとします。このリストは、ツリーを順番にトラバースする際のリーフノードを表しています。ここで、内部ノードには2つの子があり、それらの値は、左側のサブツリーの最大の葉の値と右側のサブツリーの最大の葉の値の積と同じです。値の合計が最小のツリーの合計を見つける必要があります

したがって、入力がnums =[3、5、10]の場合、出力は83になります。

これを解決するには、次の手順に従います。

• res：=numsのすべての要素の合計
• numsのサイズが1より大きい場合は
  • i：=numsの最小要素のインデックス
  • left：=nums [i-1]（i> 0の場合）それ以外の場合は無限大
  • right：=nums [i + 1]（i
  • res：=res +（左右の最小値）* numsのi番目の要素、次にnumsからi番目の要素を削除
• return 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