बाइनरी ट्री में पथ जिनका योग k हो, उनकी संख्या गिनने का पायथन प्रोग्राम

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

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

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

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

count := एक मैप जो प्रारंभ में कुंजी 0 के लिए मान 1 रखता है
ans := 0, prefix := 0
एक फ़ंक्शन dfs() परिभाषित करें। यह node लेगा
यदि node नल नहीं है, तो
- 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