โปรแกรมหาค่าผลรวมที่ใหญ่ที่สุดของ BST ในไบนารีทรีที่กำหนดใน Python

สมมติว่าเราได้รับต้นไม้ไบนารี เราต้องค้นหาว่ามีต้นไม้การค้นหาไบนารี (BST) อยู่ในทรีย่อยของมันหรือไม่ และหาผลรวมของ BST ที่ใหญ่ที่สุด เพื่อหาผลรวม เราเพิ่มค่าของแต่ละโหนดใน BST นั้น เราคืนค่าผลรวมเป็นผลลัพธ์

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 12

BST ในไบนารีทรีที่กำหนดคือ −

ผลรวมของโหนด =12.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ค :=0
• ม :=null
• ค่า :=0
• กำหนดฟังก์ชัน recurse() นี่จะใช้โหนด
  • ถ้าโหนดไม่เป็นโมฆะ
    • left_val :=เรียกซ้ำ (ซ้ายของโหนด)
    • right_val :=เรียกซ้ำ (ด้านขวาของโหนด)
    • จำนวน :=ลบอินฟินิตี้
    • ถ้า (node.left เหมือนกับ null หรือ node.left.val <=node.val) และ ( (ทางขวาของ node เหมือนกับ null หรือ node.val <=node.right.val) แล้ว
      • จำนวน :=left_val + right_val + 1
    • ถ้านับ> c แล้ว
      • c :=นับ
      • m :=โหนด
    • จำนวนคืนสินค้า
  • คืน 0
• กำหนดฟังก์ชันที่คำนวณ_sum() สิ่งนี้จะหยั่งราก
  • ถ้ารูทไม่เหมือนกับ null แล้ว
    • calculate_sum(ด้านซ้ายของรูท)
    • ค่า :=ค่า + ค่าของรูท
    • calculate_sum(ทางขวาของรูท)
• recurse(root)
• คำนวณ_sum(ม.)
• คืนค่า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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

ผลลัพธ์

12