โปรแกรมหาผลรวมสูงสุดของโหนดไม่ติดกันในต้นไม้ใน Python

สมมติว่าเรามีต้นไม้ทวิภาค หาผลรวมสูงสุดของค่าโหนดที่เลือกได้ โดยไม่มีสองโหนดที่ติดกัน (parent-child) ถูกเลือกพร้อมกัน

ตัวอย่าง: จากภาพ ผลลัพธ์ 17 (เลือก 10, 4, 3 ซึ่งไม่ติดกัน)

ขั้นตอนการแก้ปัญหา (Tree DP)

1. ฟังก์ชัน f(node) คืนค่าคู่ (take, not_take):
   • ถ้า node เป็น None: คืนค่า (0, 0)
   • (a, b) = f(node.left), (c, d) = f(node.right)
   • คืนค่า (max(node.val + b + d, a + c), a + c)
     • take = เลือกโหนดนี้ + ไม่เลือกลูกทั้งสอง
     • not_take = ไม่เลือกโหนดนี้ + เลือกได้อย่างอิสระจากลูก
2. จากเมธอดหลัก เรียก f(root)[0]

ตัวอย่างโค้ด Python

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

def f(node):
    if not node:
        return 0, 0
    a, b = f(node.left)
    c, d = f(node.right)
    return max(node.val + b + d, a + c), a + c

class Solution:
    def solve(self, root):
        return f(root)[0]

ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10)
root.left.left = TreeNode(4)
root.left.right = TreeNode(3)
print(ob.solve(root))  # Output: 17

อินพุต / เอาต์พุต

Input: ต้นไม้ตามโค้ดตัวอย่าง

Output: 17