जांचें कि क्या दिए गए योग के साथ एक ट्रिपल बीएसटी में पायथन में मौजूद है

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

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

टोटल =12, तो आउटपुट ट्रू होगा।

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

• temp_list :=शून्य से आरंभ की गई एक नई सूची
• क्रम में पेड़ को पार करें और उसे temp_list में डालें
• मैं के लिए 0 से (temp_list - 2 का आकार), 1 से बढ़ाएँ
  • बाएं:=i + 1
  • दाएं:=temp_list का आकार - 1
  • बाएं <दाएं, करते हैं
    • यदि temp_list[i] + temp_list[left] + temp_list[right] योग के समान है, तो
      • सही लौटें
    • अन्यथा जब temp_list[i] + temp_list[left] + temp_list[right] <योग शून्य नहीं है, तब
      • बाएं:=बाएं + 1
    • अन्यथा,
      • दाएं:=दाएं - 1
• झूठी वापसी

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

class TreeNode:
   def __init__(self, value):
      self.value = value
      self.right = None
      self.left = None
def traverse_inorder(tree_root, inorder):
   if tree_root is None:
      return
   traverse_inorder(tree_root.left, inorder)
   inorder.append(tree_root.value)
   traverse_inorder(tree_root.right, inorder)
def solve(tree_root, sum):
   temp_list = [0]
   traverse_inorder(tree_root, temp_list)
   for i in range(0, len(temp_list) - 2, 1):
      left = i + 1
      right = len(temp_list) - 1
      while(left < right):
         if temp_list[i] + temp_list[left] + temp_list[right] == sum:
            return True
         elif temp_list[i] + temp_list[left] + temp_list[right] < sum:
            left += 1
         else:
            right -= 1
   return False
tree_root = TreeNode(5)
tree_root.left = TreeNode(3)
tree_root.right = TreeNode(7)
tree_root.left.left = TreeNode(2)
tree_root.left.right = TreeNode(4)
tree_root.right.left = TreeNode(6)
tree_root.right.right = TreeNode(8)
print(solve(tree_root, 12))

इनपुट

tree_root = TreeNode(5)
tree_root.left = TreeNode(3)
tree_root.right = TreeNode(7)
tree_root.left.left = TreeNode(2)
tree_root.left.right = TreeNode(4)
tree_root.right.left = TreeNode(6)
tree_root.right.right = TreeNode(8)
12

आउटपुट

True