Minimum Cost Tree From Leaf Values: ต้นทุนต่ำสุดของต้นไม้จาก Leaf Values

โจทย์

กำหนด array arr ของจำนวนเต็มบวก สร้าง Binary Tree ที่:

1. โหนดแต่ละตัวมีลูก 0 หรือ 2 ตัว (Full Binary Tree)
2. Leaf nodes (inorder) = arr ตามลำดับ
3. Non-leaf node value = ผลคูณของ max leaf ใน left subtree × max leaf ใน right subtree

หา Minimum Sum ของ non-leaf nodes ทั้งหมด

ตัวอย่าง: arr = [6,2,4] → 2 ต้นไม้เป็นไปได้:

Tree 1:        Tree 2:
   24             32
  /  \           /  \
 6   12         8    4
    /  \       / \
   2    4     6   2
Sum = 12+24=36   Sum = 8+24=32 ← Minimum

วิธีแก้ 1: DP (Interval DP) - O(n³)

dp[i][j] = min cost สำหรับ subarray arr[i:j+1]

class Solution:
    def mctFromLeafValues(self, arr: list[int]) -> int:
        n = len(arr)
        memo = {}
        
        def dp(i, j):
            if i >= j:
                return 0
            if (i, j) in memo:
                return memo[(i, j)]
            
            res = float('inf')
            for k in range(i, j):
                # Split at k: left = i..k, right = k+1..j
                left_max = max(arr[i:k+1])
                right_max = max(arr[k+1:j+1])
                cost = left_max * right_max
                total = dp(i, k) + dp(k+1, j) + cost
                res = min(res, total)
            
            memo[(i, j)] = res
            return res
        
        return dp(0, n-1)

# ทดสอบ
ob = Solution()
print(ob.mctFromLeafValues([6,2,4]))  # 32

วิธีแก้ 2: Monotonic Stack (Greedy) - O(n) ⭐ Optimal

Key Insight: Non-leaf node = product of 2 adjacent "peaks" ในการ merge เราต้องการ merge ค่าน้อยกับค่ามากที่สุดเท่าที่จะทำได้ (เพื่อลด product)

ใช้ Monotonic Decreasing Stack:

1. Push elements เข้า stack
2. เมื่อ element ใหม่ > stack top: pop top, cost += popped × min(new_top, current)
3. ท้ายสุด: pop ทั้ง stack คูณกับ next element

class Solution:
    def mctFromLeafValues(self, arr: list[int]) -> int:
        stack = [float('inf')]  # Sentinel
        total_cost = 0
        
        for num in arr:
            # Pop while current >= top (merge small with smaller neighbor)
            while stack[-1] <= num:
                mid = stack.pop()
                total_cost += mid * min(stack[-1], num)
            stack.append(num)
        
        # Clean up remaining stack
        while len(stack) > 2:
            total_cost += stack.pop() * stack[-1]
        
        return total_cost

# ทดสอบ
ob = Solution()
print(ob.mctFromLeafValues([6,2,4]))       # 32
print(ob.mctFromLeafValues([4,11,5,10]))   # 220
print(ob.mctFromLeafValues([1,2,3,4]))     # 20

Output

32
220
20

การทำงานของ Stack (ตัวอย่าง [6,2,4])

stack=[inf]
num=6: stack=[inf, 6]
num=2: stack=[inf, 6, 2]
num=4: 4 > 2 → pop 2, cost += 2 * min(6,4) = 8, stack=[inf,6]
      4 < 6 → push, stack=[inf,6,4]
End: pop 4, cost += 4*6 = 24 → total=32
pop 6, cost += 6*inf (skip sentinel)

Complexity

• DP: O(n³) time, O(n²) space
• Monotonic Stack: O(n) time, O(n) space ⭐

สรุป

Minimum Cost Tree From Leaf Values แก้ได้ด้วย Monotonic Stack แบบ Greedy O(n) จุดสำคัญคือ merge ค่าน้อยกับ neighbor ที่น้อยกว่าเสมอ (local optimal = global optimal)

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ