পাইথনে বাইনারি ট্রিতে যেসব পথের যোগফল k তাদের সংখ্যা গুনার প্রোগ্রাম

मान लीजिए हमारे पास एक बाइनरी ट्री और एक अन्य मान k है, हमें उन अद्वितीय नोड-टू-सबचाइल्ड पथों की संख्या ढूंढनी है जिनका योग k के बराबर है।

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

और k = 5, तो आउटपुट 2 होगा, क्योंकि पथ हैं [2, 3] और [1, 4]

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

• count := एक मैप जो प्रारंभ में कुंजी 0 के लिए मान 1 रखता है
• ans := 0, prefix := 0
• एक फंक्शन dfs() परिभाषित करें। यह node लेगा
• अगर node null नहीं है, तो
  • prefix := prefix + node का मान
  • ans := ans + (count[prefix - target], अगर यह उपलब्ध नहीं है तो 0 होगा)
  • count[prefix] := count[prefix] + 1
  • dfs(node का बायां)
  • dfs(node का दायां)
  • count[prefix] := count[prefix] - 1
  • prefix := prefix - node का मान
• मुख्य विधि से, निम्नलिखित करें
• dfs(root)
• ans लौटाएं

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:

উদাহরণ

from collections import Counter
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, target):
        count = Counter([0])
        ans = prefix = 0
        def dfs(node):
            nonlocal ans, prefix
            if node:
                prefix += node.val
                ans += count[prefix - target]
                count[prefix] += 1
                dfs(node.left)
                dfs(node.right)
                count[prefix] -= 1
                prefix -= node.val
        dfs(root)
        return ans

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

ইনপুট

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

আউটপুট

2