首页 > 其他分享 >LeetCode/叶值的最小代价生成树

LeetCode/叶值的最小代价生成树

时间:2023-05-31 23:37:46浏览次数:46  
标签:arr cur int 叶值 top 节点 res 代价 LeetCode

给你一个正整数数组 arr,考虑所有满足以下条件的二叉树:
每个节点都有 0 个或是 2 个子节点。
数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。
每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
在所有这样的二叉树中,返回每个非叶节点的值的最小可能总和。

1. 贪心+单调栈

该问题不适合列举所有可能得二叉树进行判断
通过试图贪心构造最优的二叉树
观察到节点的度只能为0或2,最终非叶子节点数为n-1
所以必然会进行n-1次合并,优先对小的进行合并
这里使用单调栈

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        stack<int> s;
        int n = arr.size();
        int res = 0;
        //单调栈,当前数大于栈顶时,把栈前面所有小的数合并掉
        for(int i=0;i<n;i++){//遍历所有数
           if(!s.empty()&&arr[i]>=s.top()){
               int cur = s.top(); s.pop();//把前面小于等于arr[i]的数全部合并掉
               while(!s.empty()&&arr[i]>=s.top()){
                   res+=cur*s.top();//合并
                   cur = s.top(); s.pop();
               }
               res+=cur*arr[i];//将arr[i]与最终结果合并
           }
            s.push(arr[i]);
        }
        int cur = s.top();s.pop();
        while(!s.empty()){
            res+=cur*s.top();
            cur =s.top(); s.pop();
        }
        return res;
    }
};

标签:arr,cur,int,叶值,top,节点,res,代价,LeetCode
From: https://www.cnblogs.com/929code/p/17447649.html

相关文章

  • 1130. 叶值的最小代价生成树
    题目链接:1130.叶值的最小代价生成树方法:dp解题思路状态表示集合:\(dp[i][j]\)表示子数组\([i,j]\)能构成的所有合法的二叉树集合;属性:\(dp[i][j]\)的值表示集合中,二叉树非叶节点值和的其中最小值。状态计算集合划分:将子数组\([i,j]\),划分为\([i,k]\)和\([k......
  • LeetCode 96.不同的二叉搜索树
    1.题目:给你一个整数n,求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种?返回满足题意的二叉搜索树的种数。示例1:输入:n=3输出:5示例2:输入:n=1输出:1来源:力扣(LeetCode)链接:https://leetcode.cn/problems/unique-binary-search-trees著作权归领扣网络所有......
  • LeetCode 343.整数拆分
    1.题目:给定一个正整数 n ,将其拆分为k个正整数的和( k>=2 ),并使这些整数的乘积最大化。返回你可以获得的最大乘积 。示例1:输入:n=2输出:1解释:2=1+1,1×1=1。示例 2:输入:n=10输出:36解释:10=3+3+4,3× 3× 4=36。来源:力扣(LeetCo......
  • 图解LeetCode——102. 二叉树的层序遍历
    一、题目给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地,从左到右访问所有节点)。二、示例2.1>示例1:【输入】root=[3,9,20,null,null,15,7]【输出】[[3],[9,20],[15,7]]2.2>示例2:【输入】root=[1]【输出】[[1]]2.3>示例3:【输入】root=[]......
  • [leetcode每日一题]5.31
    1130. 叶值的最小代价生成树提示中等324相关企业给你一个正整数数组 arr,考虑所有满足以下条件的二叉树:每个节点都有 0 个或是 2 个子节点。数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。在所有这......
  • 二刷Leetcode-Days08
    栈与队列:/***20.有效的括号*@params*@return*/publicbooleanisValid(Strings){Deque<Character>deque=newLinkedList<>();for(inti=0;i<s.length();i++){charch=s.charAt......
  • 图解LeetCode——146. LRU 缓存
    一、题目请你设计并实现一个满足 LRU(最近最少使用)缓存约束的数据结构。实现LRUCache类:LRUCache(intcapacity)以正整数作为容量 capacity初始化LRU缓存intget(intkey)如果关键字key存在于缓存中,则返回关键字的值,否则返回-1。voidput(intkey,intva......
  • leetcode
    1python常用函数1.1排序函数原地排序nums.sort()不改变原列表有返回值new=sorted(nums)importfunctools#一维数组排序nums=[2,1,3,4,5]defcompare_udf(x,y):#x-y升序#y-x降序returnx-y##python2nums.sort(cmp=compar......
  • leetcode 693. Binary Number with Alternating Bits
    Givenapositiveinteger,checkwhetherithasalternatingbits:namely,iftwoadjacentbitswillalwayshavedifferentvalues.Example1:Input:5Output:TrueExplanation:Thebinaryrepresentationof5is:101Example2:Input:7Output:FalseExplanation......
  • leetcode 637. Average of Levels in Binary Tree
    Givenanon-emptybinarytree,returntheaveragevalueofthenodesoneachlevelintheformofanarray.Example1:Input:3/\920/\157Output:[3,14.5,11]Explanation:Theaveragevalueofnodesonlevel0is3,onlevel......