पायथन का उपयोग करके अच्छे लीफ नोड्स जोड़े की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी ट्री है। और दूसरा मान दूरी d. दो अलग-अलग लीफ नोड्स की एक जोड़ी को अच्छा कहा जाता है, जब इन दो नोड्स के बीच का सबसे छोटा रास्ता छोटा या दूरी d के समान होता है।

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

और दूरी d =4, तो आउटपुट 2 होगा क्योंकि जोड़े (8,7) और (5,6) हैं क्योंकि उनकी पथ लंबाई दूरी 2 है, लेकिन (7,5) या (8,6) या अन्य जोड़े हैं अच्छे नहीं हैं क्योंकि उनके पथ की लंबाई 5 है जो d =4 से बड़ी है

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

• सोल:=0

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

• अगर रूट शून्य है, तो

  • एक नई सूची लौटाएं

• अगर जड़ पत्ती है, तो

  • एक जोड़ी के साथ एक सरणी लौटाएं [0, 0]

• अन्यथा,

  • cur :=एक नई सूची

  • एल:=उपयोग (रूट के बाएं)

  • आर:=उपयोग (रूट का अधिकार)

  • l में प्रत्येक n के लिए, करें

    • n[1] :=n[1] + 1

  • r में प्रत्येक n के लिए, करें

    • n[1] :=n[1] + 1

  • r में प्रत्येक n के लिए, करें

    • l में प्रत्येक n1 के लिए, करें

      • यदि n[1] + n1[1] <=d, तो

        • सोल:=सोल + 1

  • वापसी एल+आर

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

• उपयोग (रूट)

• वापसी सोल

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

उदाहरण

class TreeNode:
def __init__(self, val=0, left=None, right=None):
   self.val = val
   self.left = left
   self.right = right
class Solution:
   def __init__(self):
      self.sol = 0
   def solve(self, root, d):
      def util(root):
         if not root:
            return []
         if not root.left and not root.right:
            return [[0, 0]]
         else:
            cur = []
            l = util(root.left)
            r = util(root.right)
            for n in l:
               n[1] += 1
            for n in r:
               n[1] += 1
            for n in r:
               for n1 in l:
                  if n[1] + n1[1] <= d:
                     self.sol += 1
            return l+r
      util(root)
      return self.sol
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
d = 4
ob = Solution()
print(ob.solve(root, d))

इनपुट

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
d = 4

आउटपुट

2