Chương trình tìm tổng số tối đa các nút không liền kề của một cây trong Python

Giả sử chúng ta có một cây nhị phân, chúng ta phải tìm tổng lớn nhất của các giá trị có thể nhận được vì không có hai giá trị nào có thể là cha và con liền kề.

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

thì đầu ra sẽ là 17 vì 10, 4, 3 không liền kề nhau.

Để 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 f (). Điều này sẽ lấy nút
• nếu nút là null, thì
  • return (0, 0)
• (a, b):=f (bên trái của nút)
• (c, d):=f (bên phải của nút)
• trả về một cặp (giá trị lớn nhất của nút + b + d và a + c, a + c)
• từ phương thức chính gọi f (root) và trả về giá trị đầu tiên của nó

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
def f(node):
   if not node:
      return 0, 0
   a, b = f(node.left)
   c, d = f(node.right)
   return max(node.val + b + d, a + c), a + c
class Solution:
   def solve(self, root):
      return f(root)[0]
ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10) root.left.left = TreeNode(4) root.left.right = TreeNode(3) print(ob.solve(root))

Đầu vào

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10)
root.left.left = TreeNode(4)
root.left.right = TreeNode(3)

Đầu ra

17