Chương trình tìm ra giá trị tổng lớn nhất của BST trong cây nhị phân đã cho bằng Python

Giả sử chúng ta được cung cấp một cây nhị phân. Ta phải tìm xem có tồn tại cây tìm kiếm nhị phân (BST) trong các cây con của nó hay không và tìm ra tổng của BST lớn nhất. Để tìm ra tổng, chúng tôi thêm các giá trị của mỗi nút trong BST đó. Chúng tôi trả về giá trị tổng dưới dạng đầu ra.

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

thì đầu ra sẽ là 12.

BST trong cây nhị phân đã cho là -

tổng các nút =12.

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

• c:=0
• m:=null
• giá trị:=0
• Định nghĩa một hàm recurse (). Điều này sẽ lấy nút
  • nếu nút không rỗng, thì
    • left_val:=recurse (bên trái của nút)
    • right_val:=recurse (bên phải của nút)
    • count:=âm vô cực
    • if (node.left giống với null hoặc node.left.val <=node.val) và ((bên phải của node giống với null hoặc node.val <=node.right.val), thì
      • số lượng:=left_val + right_val + 1
    • nếu đếm> c, thì
      • c:=count
      • m:=nút
    • số lượng trả lại
  • trả về 0
• Xác định một hàm tính_sum (). Điều này sẽ bắt rễ
  • nếu root không giống với null, thì
    • math_sum (bên trái của thư mục gốc)
    • giá trị:=giá trị + giá trị của gốc
    • math_sum (bên phải của thư mục gốc)
• đệ quy (root)
• math_sum (m)
• giá trị trả về

Ví dụ

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

class TreeNode:
   def __init__(self, val, left = None, right = None):
      self.val = val
      self.left = left
      self.right = right

def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)

def make_tree(elements):
   Tree= TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree

def solve(root):
   c, m, value = 0, None, 0
   def recurse(node):
      if node:
         nonlocal c, m
         left_val = recurse(node.left)
         right_val = recurse(node.right)
         count = -float("inf")
         if (node.left == None or node.left.val <= node.val) and (node.right == None or node.val <= node.right.val):
            count = left_val + right_val + 1
         if count > c:
            c = count
            m = node
         return count
      return 0
   def calculate_sum(root):
      nonlocal value
      if root is not None:
         calculate_sum(root.left)
         value += root.val
         calculate_sum(root.right)
   recurse(root)
   calculate_sum(m)
   return value

tree = make_tree([1, 4, 6, 3, 5])
print(solve(tree))

Đầu vào

tree = make_tree([1, 4, 6, 3, 5])
print(solve(tree))

Đầu ra

12