Chương trình tìm tổng số cây tối thiểu từ danh sách các lá trong python

Giả sử chúng ta có một danh sách các số được gọi là nums. Danh sách này đại diện cho các nút lá trong đường đi ngang qua không gian của một cây. Ở đây các nút bên trong có 2 nút con và giá trị của chúng bằng tích của giá trị lá lớn nhất của cây con bên trái của nó và giá trị lá lớn nhất của cây con bên phải của nó. Chúng ta phải tìm tổng của cây với tổng các giá trị nhỏ nhất của nó

Vì vậy, nếu đầu vào là nums =[3, 5, 10], thì đầu ra sẽ là 83.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• res:=tổng của tất cả các phần tử trong nums
• trong khi kích thước của nums> 1, thực hiện
  • i:=chỉ số của phần tử tối thiểu của nums
  • left:=nums [i - 1] khi i> 0, ngược lại là vô cực
  • right:=nums [i + 1] khi tôi
  • res:=res + (tối thiểu bên trái và bên phải) * phần tử thứ i trong số nums, sau đó xóa phần tử thứ i khỏi nums
• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Mã mẫu

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))

Đầu vào

[3, 5, 10]

Đầu ra

83