পাইথনে লিফ নোডের তালিকা থেকে ন্যূনতম যোগফল वाले ট্রি বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি সংখ্যার তালিকা nums আছে। এই তালিকাটি একটি ট্রির লিফ নোডগুলকে ইনঅর্ডার ট্রাভার্সালে প্রতিনিধিত্ব করে। এখানে ইন্টারনাল নোডগুলোর দুটি চাইল্ড থাকে এবং তাদের মান হচ্ছে তার বাম সাবট্রির সবচেয়ে বড় লিফ মান এবং ডান সাবট্রির সবচেয়ে বড় লিফ মানের গুণফল। আমাদের কাজ হল ন্যূনতম যোগফল বিশিষ্ট ট্রির মোট যোগফল বের করা।

উদাহরণস্বরূপ, যদি ইনপুট হয় nums = [3, 5, 10], তবে আউটপুট হবে 83।

• res := nums-এর সব 엘িমেন্টের যোগফল
• len(nums) > 1 হলে লুপ চালান:
  • i := nums-এ ন্যূনতম এলিমেন্টের ইনডেক্স
  • left := nums[i-1] যদি i > 0 অন্যথায় ইনফিনিটি
  • right := nums[i+1] যদি i < len(nums)-1 অন্যথায় ইনফিনিটি
  • res := res + min(left, right) * nums.pop(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