Chương trình tìm độ dài đường đi có tổng chẵn dài nhất trong cây nhị phân trong Python

Cho một cây nhị phân, tìm độ dài đường đi (số nút) dài nhất mà tổng giá trị các nút trên đường đi là số chẵn.

Ví dụ: cây như hình → đường đi [5, 2, 4, 8, 5] có tổng 24 (chẵn), độ dài 5.

Giải thuật (DFS trả về cặp giá trị)

Mỗi nút trả về một cặp (even_len, odd_len) là độ dài đường đi dài nhất bắt đầu từ nút đó đi xuống có tổng chẵn/lẻ.

• Nếu nút rỗng: trả về (0, -inf).
• Đệ quy lấy cặp từ con trái và con phải.
• Nếu giá trị nút là lẻ:
  • Cập nhật đáp án toàn cục: max(ans, left_odd + right_even + 1, left_even + right_odd + 1).
  • Trả về (max(left_odd, right_odd) + 1, max(left_even, right_even) + 1).
• Nếu giá trị nút là chẵn:
  • Cập nhật: max(ans, left_even + right_even + 1, left_odd + right_odd + 1).
  • Trả về (max(left_even, right_even) + 1, max(left_odd, right_odd) + 1).

Mã nguồn Python

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

class Solution:
    def solve(self, root):
        self.ans = 0
        def dfs(node):
            if not node:
                return 0, float("-inf")
            left_0, left_1 = dfs(node.left)
            right_0, right_1 = dfs(node.right)
            if node.val & 1:  # odd
                self.ans = max(self.ans, left_1 + right_0 + 1, left_0 + right_1 + 1)
                return max(left_1 + 1, right_1 + 1, 0), max(left_0 + 1, right_0 + 1)
            else:  # even
                self.ans = max(self.ans, left_0 + right_0 + 1, left_1 + right_1 + 1)
                return max(left_0 + 1, right_0 + 1, 0), max(left_1 + 1, right_1 + 1)
        dfs(root)
        return self.ans

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(5)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(5)
print(ob.solve(root))  # Output: 5

Đầu vào

root = TreeNode(2) ...

Đầu ra

5