โปรแกรมหาความต่างระหว่างโหนดและลูกหลานใน Python

สมมติว่ามี binary tree ต้องการหาความต่างสัมบูรณ์มากที่สุดระหว่างโหนดกับลูกหลานของมัน

ตัวอย่าง: ต้นไม้ที่มีโหนด 8 และ 1 ความต่าง 7

ขั้นตอนการแก้ปัญหา

1. ฟังก์ชัน dfs(node) คืน [min_val, max_val] ของ subtree:
   • ถ้า node ว่าง: คืน [inf, -inf]
   • left = dfs(node.left), right = dfs(node.right)
   • res = [min(left[0], right[0], node.val), max(left[1], right[1], node.val)]
   • ans = max(ans, node.val - res[0], res[1] - node.val)
   • คืน res
2. ans = 0, เรียก dfs(root), คืน ans

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

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))

อินพุต

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)

เอาต์พุต

7