leetcode 1130. 叶值的最小代价生成树

leetcode 1130. 叶值的最小代价生成树

三月 22, 2020

leetcode 1130. 叶值的最小代价生成树

给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：

每个节点都有 0 个或是 2 个子节点。
数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。（知识回顾：如果一个节点有 0 个子节点，那么该节点为叶节点。）
每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。

示例：

输入：arr = [6,2,4]
输出：32
解释：
有两种可能的树，第一种的非叶节点的总和为 36，第二种非叶节点的总和为 32。

  24            24
 /  \          /  \
12   4        6    8
/  \               / \
6    2             2   4

解法

一个数组分为两半,因为中序遍历,这两半分别是左子树和右子树.所以只需要计算出左子树和右子树的最小和.这个左子树和右子树又可以拆成两半,这样就是4份,如此递归下去.
3,4,2,1->[3]和[4,2,1],对于4,2,1->[4]和[2,1].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int mctFromLeafValues(int[] arr) {
        if(arr.length==0)return 0;
        target=new int[arr.length][arr.length];
        return getSum(arr,0,arr.length-1);
    }
    public int[][]target;//用来存储每次求过的子树的和,加快效率
    public int getSum(int[]arr,int start,int end){
        if(start==end){
            return 0;
        }
        if(target[start][end]!=0)
            return target[start][end];
        int minSum=Integer.MAX_VALUE;
        for(int i=start;i<end;i++){
            int tmp=getSum(arr,start,i)+getSum(arr,i+1,end)+getMax(arr,start,i)*getMax(arr,i+1,end); 
            minSum=Math.min(minSum,tmp);
        }
        target[start][end]=minSum;
        return minSum;
    }
    public int getMax(int[]arr,int start,int end){
        //在范围内部求出来最大的数
        int max=0;
        for(int i=start;i<=end;i++){
            if(arr[i]>max)max=arr[i];
        }
        return max;
    }
}

leetcode 62/100