पायथन में एक बाइनरी ट्री पर k-लंबाई पथ खोजने का कार्यक्रम

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

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

k =3, तो आउटपुट 4 होगा, क्योंकि पथ [12,8,3], [12,8,10], [8,12,15], [3,8,10] हैं।

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

• फ़ंक्शन को परिभाषित करें dfs() । यह नोड लेगा

  • यदि नोड शून्य है, तो

    • 1 और k-1 संख्या 0s के साथ एक सूची लौटाएं

  • बाएँ:=dfs (नोड के बाएँ)

  • दाएँ:=dfs (नोड के दाएँ)

  • मेरे लिए 0 से K की सीमा में, करें

    • उत्तर:=उत्तर + बाएँ [i] * दाएँ [K - 1 - i]

  • res :=0s के आकार K की सूची

  • रेस [0]:=1, रेस [1]:=1

  • मैं के लिए 1 से के -1 की सीमा में, करो

    • रेस [i + 1]:=रेस [i + 1] + बाएं [i]

    • रेस [i + 1]:=रेस [i + 1] + दाएं [i]

  • रिटर्न रेस

• मुख्य विधि से, निम्न कार्य करें-

• उत्तर :=0

• 
  

• dfs(रूट)

• 
  

• वापसी उत्तर

  
  

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

उदाहरण

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, K):
      def dfs(node):
         if not node:
            return [1] + [0] * (K-1)
         left = dfs(node.left)
         right = dfs(node.right)
         for i in range(K):
            self.ans += left[i] * right[K - 1 - i]
         res = [0] * K
         res[0] = res[1] = 1
         for i in range(1, K - 1):
            res[i + 1] += left[i]
            res[i + 1] += right[i]
         return res
      self.ans = 0
      dfs(root)
      return self.ans
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, 3))

इनपुट

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

आउटपुट

4