Chương trình tìm tổng lớn nhất của các nút không liền kề trong cây bằng Python

Cho cây nhị phân, tìm tổng lớn nhất của các giá trị nút sao cho không có hai nút nào là cha-con trực tiếp (không liền kề).

Ví dụ: cây cho kết quả 17 (chọn 10, 4, 3).

Quy trình giải quyết (Tree DP)

1. Định nghĩa hàm f(node) trả về cặp (take, not_take):
   • take: tổng lớn nhất nếu chọn nút này.
   • not_take: tổng lớn nhất nếu không chọn nút này.
2. Nếu nút null: trả về (0, 0).
3. Đệ quy cho con trái (a, b) và con phải (c, d).
4. take = node.val + b + d (chọn nút này thì không chọn con).
5. not_take = a + c (không chọn nút này thì có thể chọn hoặc không chọn con).
6. Trả về (max(take, not_take), not_take).
7. Kết quả là phần tử đầu của f(root).

Ví dụ mã nguồn

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

Đầu vào

root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(10) root.left.left = TreeNode(4) root.left.right = TreeNode(3)

Đầu ra

17