Chương trình tìm sự khác biệt giữa nút và nút con trong Python

Giả sử chúng ta có một cây nhị phân, chúng ta phải tìm ra sự khác biệt tuyệt đối lớn nhất giữa bất kỳ nút nào và các nút con của nó.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 7 vì sự khác biệt tuyệt đối lớn nhất là giữa các nút 8 và 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm dfs (). Điều này sẽ lấy nút
• nếu nút không rỗng, thì
  • trả về một danh sách có vô cực dương và âm
• left:=dfs (left of node)
• right:=dfs (bên phải của nút)
• res:=một cặp với (tối thiểu bên trái [0], bên phải [0] và giá trị của nút và tối đa bên trái [1], bên phải [1] và giá trị của nút)
• ans:=tối đa ans, (giá trị của nút - res [0]) và (res [1] - giá trị của nút)
• trả lại res
• Từ phương pháp chính, hãy thực hiện như sau -
• ans:=0
• dfs (gốc)
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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