পাইথনের একটি প্রদত্ত বাইনারি ট্রিতে একটি BST-এর বৃহত্তম সমষ্টির মান খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি গাছ দেওয়া হয়েছে। এর সাবট্রিতে বাইনারি সার্চ ট্রি (BST) আছে কিনা তা খুঁজে বের করতে হবে এবং সবচেয়ে বড় BST-এর যোগফল বের করতে হবে। যোগফল বের করতে, আমরা সেই BST-তে প্রতিটি নোডের মান যোগ করি। আমরা আউটপুট হিসাবে যোগফলের মান ফেরত দিই।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 12।

প্রদত্ত বাইনারি ট্রিতে BST হল −

নোডের যোগফল =12।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

c :=0
m :=শূন্য
মান :=0
একটি ফাংশন recurse() সংজ্ঞায়িত করুন। এটি নোড
- যদি নোড নাল না হয়, তাহলে
  - left_val :=recurse(নোডের বামে)
  - right_val :=recurse (নোডের ডানদিকে)
  - গণনা :=ঋণাত্মক অসীম
  - যদি (node.left null বা node.left.val <=node.val) এবং( (নোডের ডানদিকে null বা node.val <=node.right.val সমান), তাহলে
    - গণনা :=left_val + right_val + 1
  - যদি গণনা> c, তারপর
    - c :=গণনা
    - m :=নোড
  - রিটার্ন গণনা
- রিটার্ন 0
একটি ফাংশন সংজ্ঞায়িত করুন calculate_sum()। এটি রুট হবে
- যদি root null এর মত না হয়, তাহলে
  - calculate_sum(মূলের বামে)
  - মান :=মান + মূলের মান
  - calculate_sum(মূলের ডানদিকে)
রিকারস(রুট)
calculate_sum(m)
রিটার্ন মান

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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