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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告