โปรแกรมหาผลรวมต้นไม้ต่ำสุดจากรายการใบไม้ใน Python

สมมติว่ามีรายการตัวเลข nums แทนโหนดใบ (leaves) ใน inorder traversal โหนดภายในมี 2 ลูก และค่าเท่ากับผลคูณของค่าใบมากที่สุดในซ้ายและขวา ต้องการหาผลรวมของต้นไม้ที่มีผลรวมต่ำสุด

ตัวอย่าง: nums = [3, 5, 10] ผลลัพธ์คือ 83

ขั้นตอนการแก้ปัญหา

1. res = sum(nums)
2. วนลูป بينما len(nums) > 1:
   • i = index ของค่าต่ำสุดใน nums
   • left = nums[i-1] if i > 0 else inf
   • right = nums[i+1] if i < len(nums)-1 else inf
   • res += min(left, right) * nums.pop(i)
3. คืนค่า 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