पायथन में दिए गए बाइनरी ट्री में बीएसटी का सबसे बड़ा योग मूल्य खोजने का कार्यक्रम

मान लीजिए कि हमें एक बाइनरी ट्री प्रदान किया जाता है। हमें यह पता लगाना होगा कि क्या इसके सबट्री में बाइनरी सर्च ट्री (BST) मौजूद हैं और सबसे बड़े BST का योग ज्ञात करें। योग का पता लगाने के लिए, हम उस BST में प्रत्येक नोड के मान जोड़ते हैं। हम योग मान को आउटपुट के रूप में लौटाते हैं।

तो, अगर इनपुट पसंद है

तो आउटपुट 12 होगा।

दिए गए बाइनरी ट्री में BST है -

नोड्स का योग =12.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

सी :=0
एम:=शून्य
मान :=0
एक फ़ंक्शन रिकर्स () को परिभाषित करें। यह नोड लेगा
- यदि नोड रिक्त नहीं है, तो
  - बाएं_वल:=रिकर्स (नोड के बाएं)
  - right_val :=recurse(नोड के दाएं)
  - गिनती :=ऋणात्मक अनंतता
  - अगर (नोड.बाएं अशक्त या नोड.लेफ्ट.वैल <=नोड.वैल के समान है) और ((नोड का दायां अशक्त या नोड के समान है। वैल <=नोड.राइट.वैल), तो
    - गिनती:=लेफ्ट_वैल + राइट_वल + 1
  - अगर गिनती> सी, तो
    - सी :=गिनती
    - एम:=नोड
  - वापसी की संख्या
- वापसी 0
एक फ़ंक्शन को परिभाषित करें कैलकुलेट_सम() । यह जड़ लेगा
- यदि रूट शून्य के समान नहीं है, तो
  - गणना_योग(रूट के बाएं)
  - मान :=मान + मूल का मान
  - calculate_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))