current position：Home>leetcode 1130. Minimum Cost Tree From Leaf Values（python）
leetcode 1130. Minimum Cost Tree From Leaf Values（python）
20220201 02:00:14 【Wang Daya】
「 This is my participation 11 The fourth of the yuegengwen challenge 21 God , Check out the activity details ：2021 One last more challenge 」
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 inorder traversal of the tree.
 The value of each nonleaf 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 nonleaf node. It is guaranteed this sum fits into a 32bit 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 nonleaf node sum 36, and the second has nonleaf node sum 32.
Copy code
Example 2:
Input: arr = [4,11]
Output: 44
Copy code
Note:
2 <= arr.length <= 40
1 <= arr[i] <= 15
It is guaranteed that the answer fits into a 32bit signed integer (i.e., it is less than 2^31).
Copy code
analysis
According to the meaning , Given an array of positive integers arr , Consider all binary trees , bring ：
 Each node has 0 or 2 A child
 arr The value of 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 maximum leaf value in its left and right subtrees
There may be many kinds of binary trees , The problem requires us to return the minimum possible sum of the values of all non leaf nodes . The title will ensure that the sum is in 32 Bit integer within . A node is a leaf if and only if it has zero children .
First of all, through a simple observation case, we find that , Try to put a large value on the leaf node with shallow depth , Put a small value on the deeper leaf node , In this way, the result of the final multiplication will be as small as possible . There are generally three situations , Let's give three simple examples ：
 Example a ：[1,2,3] , The method of multiplication is 1 and 2 Take it first 2 , then 2 and 3 Multiply , Operate from left to right
 Example 2 ：[3,2,1] , The method of multiplication is 1 and 2 Take it first 2 , then 2 and 3 Multiply , That is, operate from right to left
 Example 3 ：[3,1,2] , take 3 and 2 The smaller value of is 2 , First pair 1 and 2 By multiplication 2 , Again 2 and 3 Multiply
Because the limit of value in the title is 1 To 15 Between , Add an extra large value before example 1 100 , Just like example 3, the law is the same , So there are two situations . We maintain a stack stack Add an extra large value at the beginning 100 , First calculate the product sum according to the logic of example 3 , Then calculate the product sum according to the logic of 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 code
Running results
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.
Copy code
Original link ：leetcode.com/problems/mi…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/02/202202010200124232.html
The sidebar is recommended
 Python avatar animation, come and generate your own animation avatar
 leetcode 1884. Egg Drop With 2 Eggs and N Floors（python）
 leetcode 1910. Remove All Occurrences of a Substring（python）
 Python and binary
 First acquaintance with Python class
 [Python data collection] scrapy book acquisition and coding analysis
 Python crawler from introduction to mastery (IV) extracting information from web pages
 Python crawler from entry to mastery (III) implementation of simple crawler
 The apscheduler module in Python implements scheduled tasks
 1379. Find the same node in the cloned binary tree (Java / C + + / Python)
guess what you like

Python connects redis, singleton and thread pool, and resolves problems encountered

Python from 0 to 1 (day 11)  Python data application 1

Python bisect module

Python + OpenGL realizes realtime interactive writing on blocks with Bspline curves

Use the properties of Python VTK implicit functions to select and cut data

Learn these 10000 passages and become a humorous person in the IT workplace. Python crawler lessons 89

leetcode 986. Interval List Intersections（python）

leetcode 1860. Incremental Memory Leak（python）

How to teach yourself Python? How long will it take?

Python Matplotlib drawing pie chart
Random recommended
 Django paging (II)
 Concurrent. For Python concurrent programming Futures or multiprocessing?
 Programmers over the age of 25 can't know a few Chinese herbal medicines. Python crawler lessons 99
 Python crawler from introduction to pit full series of tutorials (detailed tutorial + various practical combat)
 The second bullet of class in Python
 Python object oriented programming 03: class inheritance and its derived terms
 How IOS developers learn Python Programming 13  function 4
 Python crawler from introduction to mastery (VI) form and crawler login
 Python crawler from entry to mastery (V) challenges of dynamic web pages
 Deeply understand pandas to read excel, TXT, CSV files and other commands
 Daily python, Chapter 18, class
 "I just want to collect some plain photos in Python for machine learning," he said. "I believe you a ghost!"
 Django view
 Python implements filtering emoticons in text
 When winter comes, python chooses a coat with temperament for mom! Otherwise, there's really no way to start!
 Python crawler  get fund change information
 Highlight actor using Python VTK
 Python crawler actual combat: crawling southern weekend news articles
 leetcode 406. Queue Reconstruction by Height（python）
 leetcode 1043. Partition Array for Maximum Sum （python）
 Python * * packaging and unpacking details
 Python realizes weather query function
 Python from 0 to 1 (day 12)  Python data application 2 (STR function)
 Python from 0 to 1 (day 13)  Python data application 3
 Numpy common operations of Python data analysis series Chapter 8
 How to implement mockserver [Python version]
 Van * Python! Write an article and publish the script on multiple platforms
 Python data analysis  file reading
 Python data De duplication and missing value processing
 Python office automation  play with browser
 Python series tutorial 127  Reference vs copy
 Control flow in Python: break and continue
 Teach you how to extract tables in PDF with Python
 leetcode 889. Construct Binary Tree from Preorder and Postorder Traversal（python）
 leetcode 1338. Reduce Array Size to The Half（python）
 Object oriented and exception handling in Python
 How to configure load balancing for Django service
 How to embed Python in go
 Python Matplotlib drawing graphics
 Python objectoriented programming 05: concluding summary of classes and objects