current position：Home>leetcode 1130. Minimum Cost Tree From Leaf Values（python）
leetcode 1130. Minimum Cost Tree From Leaf Values（python）
2022-02-01 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 」
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.
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 code
Input: arr = [4,11] Output: 44 Copy code
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 code
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 .
class Solution(object): def mctFromLeafValues(self, arr): """ :type arr: List[int] :rtype: int """ stack =  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
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
author[Wang Daya],Please bring the original link to reprint, thank you.
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 real-time interactive writing on blocks with B-spline 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 8-9
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
- 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 9-9
- 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 object-oriented programming 05: concluding summary of classes and objects