“This is the 21st day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

describe

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.
Copy the code

Example 2:

Input: arr = [4,11]
Output: 44
Copy the code

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).
Copy the code

parsing

Given a positive integer array arR, consider all binary trees such that:

  • Each node has 0 or 2 children
  • The value of arR corresponds to the value of each leaf in the middle order traversal of the tree
  • The value of each non-leaf node is equal to the product of the largest leaf values in its left and right subtrees

There could be multiple binary trees, and they’re asking us to return the lowest possible sum of all the values of non-leaf nodes. They guarantee that the sum is within a 32-bit integer. A node is a leaf if and only if it has zero children.

First of all, through simple observation cases, we found that we should try to put the large value into the shallow leaf node, and put the small value into the deep leaf node, so that the final result of multiplication will be as small as possible. There are generally three cases. Let’s take three simple examples:

  • Example 1: [1,2,3], multiply 1 and 2 by 2, then multiply 2 and 3, that is, from left to right
  • Example 2: [3,2,1], multiply 1 and 2 by 2, and then multiply 2 and 3 from right to left
  • Example 3: [3,1,2], take the smaller value of 3 and 2 to be 2, first multiply 1 and 2 to get 2, then multiply 2 and 3

Since the limit in the problem is between 1 and 15, we put a superlarge value of 100 in front of example 1, just like in example 3, so there are two cases. We maintain a stack with a superlarge value of 100 at the top, and we compute the product sum using the logic in example 3, and then the product sum using the logic in example 2.

answer

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
            
       	      
		
Copy the code

The results

Given each node in the Python online submission list. Memory Usage: 10000 ms Given in the Python online submissions for Minimum Cost Tree From Leaf Values.Copy the code

Original link: leetcode.com/problems/mi…

Your support is my biggest motivation