在Python中查找叶子节点列表中最小树之和的程序

在Python中查找叶子节点列表中最小树之和的程序

假设我们有一个名为nums的数字列表。该列表代表树的中序遍历中的叶节点。在这里,内部节点有两个孩子,其值与其左子树的最大叶节点值和其右子树的最大叶节点值的乘积相同。我们必须找到最小值的树的值的总和

因此,如果输入为nums = [3, 5, 10],则输出将为83。

在Python中查找叶子节点列表中最小树之和的程序

要解决此问题,我们将遵循以下步骤:

  • res:nums中所有元素的总和
  • while size of nums > 1,do
    • i:nums的最小元素的索引
    • left:在i > 0时为nums [i-1],否则为正无穷
    • right:在i < size of nums-1时为nums [i + 1],否则为正无穷
    • res:res +(left和right中最小值)* nums的第i个元素,然后从nums中删除第i个元素
  • return res

让我们看以下实现以获得更好的理解:

更多Python相关文章,请阅读:Python 教程

示例代码

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程