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

Cho một cây nhị phân, tìm đường đi dài nhất chỉ chứa các nút có giá trị chẵn giữa hai nút bất kỳ trên cây.

Ví dụ, với cây như hình, kết quả là 5 ứng với đường đi [10, 2, 4, 8, 6].

Giải thuật (DFS pós-order)

1. Khởi tạo biến toàn cục ans = 0.
2. Định nghĩa hàm find(node) trả về cặp (left_max, right_max) là độ dài đường chẵn dài nhất đi xuống từ nút con trái/phải.
3. Nếu node là None: trả về (-1, -1).
4. Đệ quy tính leftCnt = max(find(node.left)) + 1, rightCnt = max(find(node.right)) + 1.
5. Nếu node.val chẵn:
   • Cập nhật ans = max(ans, leftCnt + rightCnt + 1) (đường đi qua nút hiện tại).
   • Trả về (leftCnt, rightCnt).
6. Nếu node.val lẻ:
   • Cập nhật ans = max(ans, leftCnt, rightCnt).
   • Trả về (-1, -1) (không thể mở rộng đường chẵn qua nút lẻ).
7. Gọi find(root) và trả về ans.

Ví dụ minh họa

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

class Solution:
    def solve(self, root):
        ans = 0
        def find(node):
            nonlocal ans
            if not node:
                return -1, -1
            leftCnt = max(find(node.left)) + 1
            rightCnt = max(find(node.right)) + 1
            if node.val % 2 == 0:
                ans = max(ans, leftCnt + rightCnt + 1)
                return leftCnt, rightCnt
            else:
                ans = max(ans, max(leftCnt, rightCnt))
                return -1, -1
        find(root)
        return ans

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

Đầu vào

root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)

Đầu ra

5