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

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

इसलिए, यदि इनपुट है:

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

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

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

समाधान दृष्टिकोण

• पोस्ट-ऑर्डर ट्रैवर्सल का उपयोग करके प्रत्येक सबट्री की जांच करें
• ट्रैक करें कि सबट्री BST है या नहीं
• BST नोड्स की संख्या और योग गिनें
• सबसे बड़े BST का योग लौटाएं

उदाहरण कार्यान्वयन

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):
        nonlocal c, m
        if node:
            left_val = recurse(node.left)
            right_val = recurse(node.right)
            count = -float("inf")
            if (node.left is None or node.left.val <= node.val) and (node.right is 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