leetcode 1130. Minimum Cost Tree From Leaf Values（python）_王大呀呀

「這是我參與11月更文挑戰的第21天，活動詳情檢視：2021最後一次更文挑戰」

描述

Given an array arr of positive integers, consider all binary trees such that:

Each node has either 0 or 2 children;
The values of arr correspond to the values of each leaf in an in-order traversal of the tree.
The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree, respectively.

Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.

A node is a leaf if and only if it has zero children.

Example 1:

Input: arr = [6,2,4]
Output: 32
Explanation: There are two possible trees shown.
The first has a non-leaf node sum 36, and the second has non-leaf node sum 32.

Example 2:

Input: arr = [4,11]
Output: 44

Note:

2 <= arr.length <= 40
1 <= arr[i] <= 15
It is guaranteed that the answer fits into a 32-bit signed integer (i.e., it is less than 2^31).

解析

根據題意，給定一個正整數陣列 arr ，考慮所有二叉樹，使得：

每個節點有 0 或 2 個孩子
arr 的值對應於樹的中序遍歷中每個葉子的值
每個非葉節點的值分別等於其左右子樹中最大葉值的乘積

可能會有多種二叉樹，題目要求我們返回所有非葉節點的值的最小可能總和值。題目會保證該總和在 32 位整數以內。一個節點是葉子當且僅當它有零個孩子。

首先我們通過簡單的觀察案例發現，要儘量把大的值放到深度較淺的葉子結點，把小的值放到深度較深的葉子結點，這樣最後乘法的結果才會儘量小。一般有三種情況，我們舉三種簡單情況的例子：

例子一：[1,2,3] ，相乘的方法為 1 和 2 先乘得 2 ，然後 2 和 3 相乘，即從左往右操作
例子二：[3,2,1] ，相乘的方法為 1 和 2 先乘得 2 ，然後 2 和 3 相乘，即從右往左操作
例子三：[3,1,2] ，取 3 和 2 的較小值為 2 ，先對 1 和 2 相乘得 2 ，再 2 和 3 相乘

因為題目中對值的限制在 1 到 15 之間，在例子一前面加一個超大值 100 ，就和例子三一樣規律一樣，所以一共有兩種情況。我們維護一個棧 stack 在最前面加一個超大值 100 ，先按照例子三的邏輯計算乘積和，再按照例子二的邏輯計算乘積和。

解答

class Solution(object):
    def mctFromLeafValues(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        stack = [100]
        result = 0
        for current in arr:
            while stack[-1]<=current:
                drop = stack.pop()
                result += drop*(min(stack[-1], current))
            stack.append(current)
        while len(stack)>2:
            result += stack.pop() * stack[-1]
        return result

執行結果

Runtime: 28 ms, faster than 46.53% of Python online submissions for Minimum Cost Tree From Leaf Values.
Memory Usage: 13.4 MB, less than 74.26% of Python online submissions for Minimum Cost Tree From Leaf Values.

原題連結：http://leetcode.com/problems/minimum-cost-tree-from-leaf-values/

您的支援是我最大的動力