पायथन में एक बाइनरी ट्री के लीफ और नॉन-लीफ नोड्स को खोजने का कार्यक्रम

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

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

तब आउटपुट (3, 2) होगा, क्योंकि 3 पत्ते और 2 गैर-पत्ती नोड हैं।

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

• यदि n शून्य है, तो
  • वापसी (0, 0)
• यदि n का बायां भाग रिक्त है और n का दायां शून्य है, तो
  • वापसी (1, 0)
• बाएं:=हल करें(n के बाएं)
• दाएं:=हल करें(n के दाएं)
• वापसी (बाएं[0] + दाएं[0], 1 + बाएं[1] + दाएं[1])

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

उदाहरण

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, n):
      if not n:
         return 0, 0
      if not n.left and not n.right:
         return 1, 0
      left, right = self.solve(n.left), self.solve(n.right)
      return left[0] + right[0], 1 + left[1] + right[1]
ob = Solution()
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)
print(ob.solve(root))

इनपुट

root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)

आउटपुट

(3, 2)