Medium

题目描述

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

  • 每个节点都恰好有 0 个或 2 个子节点。
  • 数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。
  • 每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。

在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。保证这个和小于 2^31。

当且仅当一个节点有 0 个子节点时，该节点为叶节点。

示例 1：

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

示例 2：

输入：arr = [4,11]
输出：44

约束条件：

  • 2 <= arr.length <= 40
  • 1 <= arr[i] <= 15
  • 保证答案小于 2^31

解题思路

这道题要求构造一个二叉树，使得非叶节点值的总和最小。关键观察是：每个非叶节点的值等于其左右子树中叶节点最大值的乘积。

解法一：动态规划 设 dp[i][j] 表示子数组 arr[i...j] 构成的最小代价。对于区间 [i,j]，我们枚举所有可能的分割点 k，将区间分为 [i,k] 和 [k+1,j] 两部分。此时产生的非叶节点值为 max(arr[i...k]) * max(arr[k+1...j])，总代价为该值加上两个子问题的代价。

状态转移方程：dp[i][j] = min(dp[i][k] + dp[k+1][j] + maxLeft * maxRight)

解法二：单调栈（推荐） 这是一个更优雅的贪心解法。观察发现，每次我们应该优先合并相邻的较小元素，因为较小的元素被合并后就不会再参与后续的乘法运算。

使用单调递减栈，当遇到比栈顶大的元素时，说明栈顶元素找到了右边界，此时将其弹出并计算代价。栈顶元素会与其左右较小的邻居进行合并，代价为三者中最大值与次大值的乘积。

单调栈解法的时间复杂度更优，代码也更简洁。

代码实现

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        vector<int> stack = {INT_MAX};
        int result = 0;
        
        for (int num : arr) {
            while (stack.back() <= num) {
                int mid = stack.back();
                stack.pop_back();
                result += mid * min(stack.back(), num);
            }
            stack.push_back(num);
        }
        
        for (int i = 2; i < stack.size(); i++) {
            result += stack[i] * stack[i-1];
        }
        
        return result;
    }
};

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        stack = [float('inf')]
        result = 0
        
        for num in arr:
            while stack[-1] <= num:
                mid = stack.pop()
                result += mid * min(stack[-1], num)
            stack.append(num)
        
        for i in range(2, len(stack)):
            result += stack[i] * stack[i-1]
        
        return result

public class Solution {
    public int MctFromLeafValues(int[] arr) {
        var stack = new List<int> { int.MaxValue };
        int result = 0;
        
        foreach (int num in arr) {
            while (stack[stack.Count - 1] <= num) {
                int mid = stack[stack.Count - 1];
                stack.RemoveAt(stack.Count - 1);
                result += mid * Math.Min(stack[stack.Count - 1], num);
            }
            stack.Add(num);
        }
        
        for (int i = 2; i < stack.Count; i++) {
            result += stack[i] * stack[i - 1];
        }
        
        return result;
    }
}

var mctFromLeafValues = function(arr) {
    const stack = [Infinity];
    let result = 0;
    
    for (const num of arr) {
        while (stack[stack.length - 1] <= num) {
            const mid = stack.pop();
            result += mid * Math.min(stack[stack.length - 1], num);
        }
        stack.push(num);
    }
    
    for (let i = 2; i < stack.length; i++) {
        result += stack[i] * stack[i - 1];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
动态规划O(n³)O(n²)
单调栈O(n)O(n)

其中 n 是数组的长度。单调栈解法在时间和空间复杂度上都更优。