पथों की संख्या गिनने का कार्यक्रम जिसका योग अजगर में k है

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

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

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

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

• गिनती :=एक मानचित्र प्रारंभ में कुंजी 0 के लिए मान 1 रखता है
• उत्तर:=0, उपसर्ग:=0
• एक फ़ंक्शन को परिभाषित करें dfs() । यह नोड लेगा
• यदि नोड रिक्त नहीं है, तो
  • उपसर्ग :=उपसर्ग + नोड का मान
  • उत्तर:=उत्तर + (गिनती [उपसर्ग - लक्ष्य], यदि यह उपलब्ध नहीं है, तो यह 0) होगा
  • गिनती[उपसर्ग] :=गिनती[उपसर्ग] + 1
  • dfs(नोड के बाएं)
  • dfs(नोड के दाएं)
  • गिनती[उपसर्ग] :=गिनती[उपसर्ग] - 1
  • उपसर्ग :=उपसर्ग - नोड का मान
• मुख्य विधि से, निम्न कार्य करें
• dfs(रूट)
• वापसी उत्तर

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

उदाहरण

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