Untitled
unknown
plain_text
a month ago
1.4 kB
3
Indexable
import java.util.HashMap; import java.util.Map; public class MinSumBinaryTree { private Map<String, Integer> memo = new HashMap<>(); public int mctFromLeafValues(int[] arr) { return helper(arr, 0, arr.length - 1); } private int helper(int[] arr, int left, int right) { if (left >= right) return 0; // Base case: single leaf, no non-leaf nodes. String key = left + "," + right; if (memo.containsKey(key)) return memo.get(key); int minSum = Integer.MAX_VALUE; for (int k = left; k < right; k++) { int leftMax = getMax(arr, left, k); int rightMax = getMax(arr, k + 1, right); int cost = leftMax * rightMax + helper(arr, left, k) + helper(arr, k + 1, right); minSum = Math.min(minSum, cost); } memo.put(key, minSum); return minSum; } private int getMax(int[] arr, int left, int right) { int maxVal = 0; for (int i = left; i <= right; i++) { maxVal = Math.max(maxVal, arr[i]); } return maxVal; } public static void main(String[] args) { MinSumBinaryTree solution = new MinSumBinaryTree(); System.out.println(solution.mctFromLeafValues(new int[]{6, 2, 4})); // Output: 32 System.out.println(solution.mctFromLeafValues(new int[]{4, 11})); // Output: 44 } }
Editor is loading...
Leave a Comment