पायथन में बाइनरी ट्री का व्यास

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें पेड़ के व्यास की लंबाई की गणना करनी है। बाइनरी ट्री का व्यास वास्तव में एक पेड़ में किन्हीं दो नोड्स के बीच सबसे लंबे पथ की लंबाई है। जरूरी नहीं कि यह रास्ता जड़ से ही गुजरे। तो अगर पेड़ नीचे जैसा है, तो व्यास 3 होगा क्योंकि पथ की लंबाई [4,2,1,3] या [5,2,1,3] 3 है

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

• हम व्यास खोजने के लिए dfs का उपयोग करेंगे, उत्तर सेट करेंगे:=0
• dfs फ़ंक्शन को रूट dfs(root) से कॉल करें
• dfs नीचे dfs (नोड) की तरह काम करेगा
• यदि नोड मौजूद नहीं है, तो 0 पर लौटें
• बाएं:=dfs (रूट का बायां सबट्री), और दाएं:=dfs (रूट का राइट सबट्री)
• उत्तर:=अधिकतम उत्तर और बाएँ + दाएँ
• बाएं + 1 और दाएं + 1 का अधिकतम लौटाएं

उदाहरण

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

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         temp.left = TreeNode(data)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         temp.right = TreeNode(data)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def diameterOfBinaryTree(self, root):
      """
      :type root: TreeNode
      :rtype: int
      """
      self.ans = 0
      self.dfs(root)
      return self.ans
   def dfs(self, node):
      if not node:
         return 0
      left = self.dfs(node.left)
      right = self.dfs(node.right)
      self.ans =max(self.ans,right+left)
      return max(left+1,right+1)
root = make_tree([1,2,3,4,5])
ob1 = Solution()
print(ob1.diameterOfBinaryTree(root))

इनपुट

[1,2,3,4,5]

आउटपुट

3