1130. Minimum Cost Tree From Leaf Values

Problem Description

Given an array arr of positive integers, we need to construct a binary tree where:

1. Each node has either 0 or 2 children.
2. The values in arr correspond to the leaf nodes in an inorder traversal.
3. The value of each non-leaf node is the product of the maximum leaf value in its left and right subtrees.

The goal is to find the minimum possible sum of the values of all non-leaf nodes.

Solution Explanation

This problem can be solved efficiently using dynamic programming. The core idea is to build a solution from subproblems. We can define a 2D array dp where dp[i][j] represents the minimum cost to build a subtree from the subarray arr[i:j+1].

We also need a helper array max_arr where max_arr[i][j] stores the maximum value in the subarray arr[i:j+1]. This helps us quickly calculate the product of the maximum values in the left and right subtrees when building a new node.

The dynamic programming recurrence relation is:

dp[i][j] = min(dp[i][k] + dp[k+1][j] + max_arr[i][k] * max_arr[k+1][j]) for k in range(i, j)

This means the minimum cost for the subarray arr[i:j+1] is the minimum cost obtained by splitting the subarray at various points k, recursively solving for the subtrees, and then adding the product of their maximum values.

The base case is when i == j, meaning a single leaf node, in which case the cost is 0.

The final result will be dp[0][n-1], where n is the length of the input array.

Time and Space Complexity

• Time Complexity: O(n^3), due to the three nested loops in the dynamic programming approach.
• Space Complexity: O(n^2), to store the dp and max_arr arrays.

Code Implementation (Python)

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [[float('inf')] * n for _ in range(n)]
        max_arr = [[0] * n for _ in range(n)]
 
        # Initialize max_arr
        for i in range(n):
            max_arr[i][i] = arr[i]
            for j in range(i + 1, n):
                max_arr[i][j] = max(max_arr[i][j - 1], arr[j])
 
        # Base case: single leaf node
        for i in range(n):
            dp[i][i] = 0
 
        # Fill dp array using dynamic programming
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + max_arr[i][k] * max_arr[k + 1][j])
 
        return dp[0][n - 1]
 

This Python code efficiently implements the dynamic programming solution described above, providing a clear and concise solution to the problem. Other languages like Java, C++, Go, and TypeScript can be implemented similarly, following the same dynamic programming logic. The core structure and time/space complexity will remain consistent.