पायथन में एक बाइनरी ट्री की अधिकतम चौड़ाई खोजने का कार्यक्रम

मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें ट्री में किसी भी स्तर की अधिकतम चौड़ाई ज्ञात करनी है। यहां एक स्तर की चौड़ाई उन नोड्स की संख्या है जो सबसे बाएं नोड और सबसे दाएं नोड के बीच हो सकते हैं।

तो, अगर इनपुट

तो आउटपुट 2

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

• न्यूनतम और अधिकतम मान रखने के लिए एक नक्शा d बनाएं, न्यूनतम प्रारंभ में अनंत और अधिकतम 0

  . है

• फ़ंक्शन को परिभाषित करें dfs() । यह जड़ लेगा, स्थिति:=0, गहराई:=0

• यदि रूट शून्य है, तो कोई वापसी नहीं

• d[गहराई, 0] =न्यूनतम d[गहराई,0] और स्थिति

• d[गहराई, 1] =अधिकतम d[गहराई,1] और स्थिति

• dfs(नोड के बाएं, 2*स्थिति, गहराई+1)

• dfs(नोड का दायां, 2*pos+1, गहराई+1)

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

• dfs(रूट)

• एमएक्स:=0

• d के सभी मानों की सूची में प्रत्येक न्यूनतम-अधिकतम जोड़े के लिए, करें

  • बाएँ:=मिनट, दाएँ:=अधिकतम

  • mx:=अधिकतम mx, दाएँ-बाएँ+1

• वापसी एमएक्स

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

उदाहरण

from collections import defaultdict
   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):
   d=defaultdict(lambda: [1e9,0])
   def dfs(node, pos=0, depth=0):
      if not node:
         return
      d[depth][0]=min(d[depth][0],pos)
      d[depth][1]=max(d[depth][1],pos)
      dfs(node.left,2*pos,depth+1)
      dfs(node.right,2*pos+1,depth+1)
   dfs(root)
   mx=0
   for interval in d.values():
      l,r=interval
      mx=max(mx,r-l+1)
   return mx

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

इनपुट

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)

आउटपुट

2