পাইথনে বাইনারি ট্রি ব্যাস

ধরুন আমাদের একটি বাইনারি গাছ আছে; আমাদের গাছের ব্যাসের দৈর্ঘ্য গণনা করতে হবে। একটি বাইনারি গাছের ব্যাস আসলে একটি গাছের যেকোনো দুটি নোডের মধ্যে দীর্ঘতম পথের দৈর্ঘ্য। এই পথটি অগত্যা মূলের মধ্য দিয়ে যায় না। সুতরাং গাছটি যদি নীচের মত হয়, তাহলে ব্যাস হবে 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