สมมติว่าเรามีไบนารีทรี เราต้องหาความแตกต่างที่มากที่สุดระหว่างโหนดใดๆ กับลูกหลานของโหนด
ดังนั้นหากอินพุตเป็นแบบ
จากนั้นผลลัพธ์จะเป็น 7 เนื่องจากความแตกต่างสัมบูรณ์ที่ใหญ่ที่สุดคือระหว่างโหนด 8 และ 1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน dfs() นี่จะใช้โหนด
- ถ้าโหนดไม่เป็นโมฆะ
- ส่งคืนรายการที่มีค่าอนันต์บวกและลบ
- left :=dfs(left of node)
- ขวา :=dfs(ทางขวาของโหนด)
- res :=คู่กับ (ค่าต่ำสุดของ left[0], right[0] และค่าของ node และสูงสุดของ left[1], right[1] และค่าของ node)
- ans :=สูงสุดของ ans (ค่าของโหนด - res[0]) และ (res[1] - ค่าของโหนด)
- ผลตอบแทน
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- ตอบ :=0
- dfs(root)
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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
