Chương trình tìm chênh lệch lớn nhất giữa nút và con cháu trong Python

Mô tả bài toán

Cho cây nhị phân. Tìm giá trị tuyệt đối lớn nhất giữa một nút và bất kỳ con cháu nào của nó.

Ví dụ: cây như hình (gốc 1, trái 5, phải 3; 3 có con trái 2, phải 8; 2 có con 7,4) → đầu ra 7 (chênh lệch giữa 8 và 1).

Giải thuật (DFS hậu tự trả về min/max cây con)

1. Định nghĩa dfs(node) trả về [min_val, max_val] của cây con gốc node.
2. Nếu node rỗng: trả về [inf, -inf].
3. Gọi đệ quy trái, phải. res = [min(left[0], right[0], node.val), max(left[1], right[1], node.val)].
4. Cập nhật ans = max(ans, node.val - res[0], res[1] - node.val).
5. Trả về res.
6. Từ hàm chính: ans=0, gọi dfs(root), trả về ans.

Ví dụ mã 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):
        def dfs(node):
            if not node:
                return [float("inf"), float("-inf")]
            left = dfs(node.left)
            right = dfs(node.right)
            res = [min(left[0], right[0], node.val), max(left[1], right[1], node.val)]
            self.ans = max(self.ans, node.val - res[0], res[1] - node.val)
            return res
        self.ans = 0
        dfs(root)
        return self.ans

ob = Solution()
root = TreeNode(1)
root.left = TreeNode(5)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(8)
root.right.left.left = TreeNode(7)
root.right.left.right = TreeNode(4)
print(ob.solve(root))

Đầu vào

root = TreeNode(1) root.left = TreeNode(5) root.right = TreeNode(3) root.right.left = TreeNode(2) root.right.right = TreeNode(8) root.right.left.left = TreeNode(7) root.right.left.right = TreeNode(4)

Đầu ra

7