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

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

उदाहरण के लिए, यदि इनपुट इस तरह है:

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

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

एक फ़ंक्शन solve() परिभाषित करें। यह root, string:= खाली स्ट्रिंग लेगा
यदि root और not root.left और not root.right शून्येतर है, तो
- int(string + str(root का मान)) लौटाएं
total := 0
यदि root का बायाँ नल नहीं है, तो
- total := total + solve(root का बायाँ, string + root का मान) का संख्यात्मक मान
यदि root का दायाँ नल नहीं है, तो
- total := total + solve(root का दायाँ, string + root का मान) का संख्यात्मक मान
total लौटाएं

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

उदाहरण

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)