1130. 叶值的最小代价生成树 (opens new window)

1.动态规划

解题核心在于如何理解二叉树中序遍历叶子节点和数组每个位置上的一一对应，并将树的生成问题简化抽象成对数组操作的问题：

• 对于数组任意位置的节点而言，其左子树的所有节点一定在数组的左边，其右子树所有节点一定对应在数组的右边。
• 每个子树的所有叶子节点在数组中的对应位置是连续的。
• 非叶子节点的计算：相当于在数组上该子树的滑动窗口中，计算根节点位置左半块最大值和右边半块最大值相乘。
• 最终问题求解可以转化为，找出数组的一种子树划分方式(滑动窗口)分割方式，使得最后其代价最小。

定义dp[ i ][ j ]：表示下标 i 到下标 j 构成子树的最小代价。遍历时按照滑动窗口从小到大的顺序进行遍历，对于任意一个滑动窗口，枚举所有根节点的位置，计算左右两边子树代价之和以及当前子树根节点的值，取三者之和的最小值。其状态转移方程为：

class Solution {
    public int mctFromLeafValues(int[] arr) {
        int ans=0;
        int[][] dp =new int[arr.length][arr.length];
        //控制长度
        for(int i=0;i<arr.length;i++){
            //滑动窗口起点
            for(int k=0;k<arr.length-i;k++){
                int min=Integer.MAX_VALUE;
                for(int end=k;end<k+i;end++){
                    int left=findMax(arr,k,end);
                    int right=findMax(arr,end+1,k+i);
                    int leftsum=k==end?0:dp[k][end];
                    int rightsum=end+1==k+i?0:dp[end+1][k+i];
                    min=Math.min(min,leftsum+rightsum+left*right);
                }
                dp[k][k+i]=i==0?arr[k]:min;
            }
        }
        return dp[0][arr.length-1];
    }
    public int findMax(int[] arr,int start,int end){
        int max=arr[start];
        for(int i=start+1;i<=end;i++){
            max=Math.max(max,arr[i]);
        }
        return max;
    }
}

2.单调栈

单调栈的思路本质上是自顶向下构建树，那么构建时如何保证整棵树的代价最小？显然我们希望越大的元素它所在的层数越小越好，而小的叶子节点应该尽量往下放。基于这样的构建规则，最理性的情况就是数组是一个递减序列。

然而如果数组的中间出现了一个较大的数，因为数组的位置限定了所有元素的相对位置，所以中间出现的大数并不能直接构造在最外层树的子结点上。那么应该如何构建？其实很简单，既然不能放在树的子节点，那么可以放在左右两侧都比他小的子树的子节点上，如下图：

具体来说，栈保存数组的值，其中栈自底向上元素依次递减。当前元素分为两种情况：

• 如果比栈顶元素小，则当前元素入栈。
• 如果比栈顶元素大，则栈顶元素需要考虑和左右两边（栈顶往下一个元素）哪个元素进行组合。这里组合操作不只是两个节点处放在同一层的情况，还包括跨层之间的元素的组合。

将每次组合之后的非叶子节点的值记录在总代价和当中。按照先前提出的最小代价二叉树构造规则，越早出栈组合构建非叶子节点的元素，它所在的树的层数越高。

class Solution {
    public  int mctFromLeafValues(int[] arr) {
        int ans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(Integer.MAX_VALUE);
        for (int i : arr) {
            while (i > stack.peek()) {
                ans += stack.pop()*Math.min(i,stack.peek());
            }
            stack.push(i);
        }
        while (stack.size() > 2) {
            ans += stack.pop() * stack.peek();
        }
        return ans;
    }
}