पायथन में बाइनरी ट्री के प्रत्येक विकर्ण पथ के तत्वों का योग खोजने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें ट्री में प्रत्येक विकर्ण का योग ढूंढना है जो ऊपर से नीचे-दाएं तक जाता है।

उदाहरण के लिए, यदि इनपुट जैसा है: तो आउटपुट [27, 18, 3] होगा क्योंकि विकर्ण [12,15], [8,10], [3] हैं। इसलिए योग मान [27, 18, 3] हैं।

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

एक फंक्शन traverse() परिभाषित करें जो node, numLeft, output लेता है:

• यदि node null है, तो वापस करें
• यदि numLeft >= output का आकार, तो output के अंत में node का डेटा डालें
• अन्यथा, output[numLeft] := output[numLeft] + node का डेटा
• यदि node का बायां null नहीं है, तो traverse(node का बायां, numLeft+1, output)
• यदि node का दायां null नहीं है, तो traverse(node का दायां, numLeft, output)
• मुख्य विधि से:
  • output := एक नई सूची
  • traverse(root, 0, output)
  • output वापस करें

उदाहरण

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

class Solution:
    def solve(self, root):
        output = []
        def traverse(node, numLeft, output):
            if not node:
                return
            if numLeft >= len(output):
                output.append(node.data)
            else:
                output[numLeft] += node.data
            if node.left:
                traverse(node.left, numLeft+1, output)
            if node.right:
                traverse(node.right, numLeft, output)
        traverse(root, 0, output)
        return output

ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root))

इनपुट

root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10)

आउटपुट

[27, 18, 3]