पायथन में एक बाइनरी ट्री के पथ द्वारा गठित सभी संख्याओं का योग खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी ट्री है जहां प्रत्येक नोड में 0 से 9 तक एक अंक होता है। अब रूट से लीफ तक का प्रत्येक पथ अपने अंकों के क्रम में एक संख्या का प्रतिनिधित्व करता है। हमें पेड़ में सभी पथों द्वारा दर्शाई गई संख्याओं का योग ज्ञात करना है।

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

तो आउटपुट 680 के रूप में 46 (4 → 6), 432 (4 → 3 → 2), 435 (4 → 3 → 5) होगा, और उनका योग 913 होगा।

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

फ़ंक्शन को हल करें() परिभाषित करें। यह रूट लेगा, स्ट्रिंग:=ब्लैंक स्ट्रिंग
यदि रूट और रूट नहीं। लेफ्ट और रूट नहीं। राइट नॉन-जीरो है, तो
- रिटर्न इंट (स्ट्रिंग + स्ट्र (रूट का मान))
कुल :=0
यदि रूट का बायां भाग रिक्त नहीं है, तो
- कुल:=कुल + हल का संख्यात्मक मान (रूट के बाईं ओर, रूट का स्ट्रिंग समवर्ती मान)
यदि मूल का दायां अशक्त नहीं है, तो
- कुल :=कुल + हल का संख्यात्मक मान (रूट का दायां, रूट का स्ट्रिंग समवर्ती मान)
कुल वापसी

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

उदाहरण

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right

class Solution:
   def solve(self, root, string=""):
      if root and not root.left and not root.right:
         return int(string + str(root.val))

      total = 0
      if root.left:
         total += int(self.solve(root.left, string + str(root.val)))

      if root.right:
         total += int(self.solve(root.right, string + str(root.val)))

      return total

ob = Solution()
root = TreeNode(4)
root.left = TreeNode(6)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(5)
print(ob.solve(root))

इनपुट

root = TreeNode(4)
root.left = TreeNode(6)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(5)