Maximum Average Subtree: หา Subtree ที่มีค่าเฉลี่ยสูงสุด

โจทย์

กำหนด Binary Tree หา Maximum Average ของ subtree ใดๆ (subtree = โหนด + ทุก descendants)

Average = (ผลรวมค่าโหนดใน subtree) / (จำนวนโหนดใน subtree)

ตัวอย่าง:

    5
   / \
  6   1

อัลกอริทึม: Post-order DFS คืนค่า (sum, count)

สำหรับแต่ละโหนด คำนวณ:

• sum = sum(left) + sum(right) + node.val
• count = count(left) + count(right) + 1
• avg = sum / count → อัปเดต global max
• คืนค่า (sum, count) ให้ parent

การติดตั้ง (Python Implementation)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maximumAverageSubtree(self, root: TreeNode) -> float:
        self.max_avg = 0.0
        
        def dfs(node):
            if not node:
                return (0, 0)  # (sum, count)
            
            left_sum, left_cnt = dfs(node.left)
            right_sum, right_cnt = dfs(node.right)
            
            total_sum = left_sum + right_sum + node.val
            total_cnt = left_cnt + right_cnt + 1
            
            # Update global max average
            self.max_avg = max(self.max_avg, total_sum / total_cnt)
            
            return (total_sum, total_cnt)
        
        dfs(root)
        return self.max_avg

# Helper
def build_tree(vals):
    if not vals:
        return None
    nodes = [TreeNode(v) if v is not None else None for v in vals]
    for i, node in enumerate(nodes):
        if node:
            li, ri = 2*i+1, 2*i+2
            if li < len(nodes):
                node.left = nodes[li]
            if ri < len(nodes):
                node.right = nodes[ri]
    return nodes[0]

# ทดสอบ
ob = Solution()
root = build_tree([5,6,1])
print(ob.maximumAverageSubtree(root))  # 6.0

# ทดสอบเพิ่ม
root2 = build_tree([1,2,3,4,5,6,7])
print(ob.maximumAverageSubtree(root2))  # 7.0 (leaf 7)

Output

6.0
7.0

Complexity

• Time: O(n) - เยี่ยมทุกโหนด 1 ครั้ง
• Space: O(h) - recursion stack

สรุป

ใช้ Post-order DFS คำนวณ sum และ count ของแต่ละ subtree แล้วคำนวณ average อัปเดตค่าสูงสุด เป็นโจทย์ Tree DP แบบคลาสสิกที่แก้ได้ใน O(n)

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