Chương trình tìm tổng cây nhỏ nhất từ danh sách lá trong Python

Mô tả bài toán

Cho danh sách nums biểu diễn các nút lá theo thứ tự inorder của một cây nhị phân. Các nút nội bộ có 2 con và giá trị bằng tích của giá trị lá lớn nhất của cây con trái và cây con phải. Tìm tổng giá trị của cây có tổng nhỏ nhất.

Ví dụ: nums = [3, 5, 10] → đầu ra 83.

Giải thuật (Tham lam + Stack)

1. res = sum(nums).
2. Khi độ dài nums > 1:
   • Tìm chỉ số i của phần tử nhỏ nhất.
   • left = nums[i-1] nếu i>0 else vô cực.
   • right = nums[i+1] nếu i < len(nums)-1 else vô cực.
   • res += min(left, right) * nums.pop(i).
3. Trả về res.

Ví dụ mã 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))

Đầu vào

[3, 5, 10]

Đầu ra

83