পাইথনে একটি বাইনারি গাছের দীর্ঘতম এমনকি মান পথ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ট্রি আছে, আমাদেরকে গাছের যেকোনো দুটি নোডের মধ্যে সমান মান সমন্বিত দীর্ঘতম পথটি খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 5 কারণ দীর্ঘতম পথটি হল [10, 2, 4, 8, 6]৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• উত্তর :=0

• একটি ফাংশন সংজ্ঞায়িত করুন find()। এটি নোড গ্রহণ করবে

• যদি নোড নাল হয়, তাহলে

  • ফেরত (-1, -1)

• leftCnt :=ফাইন্ড (নোডের বামে) + 1

  এর প্রত্যাবর্তিত মানের সর্বাধিক

• rightCnt :=ফাইন্ড (নোডের ডানদিকে) + 1

  এর প্রত্যাবর্তিত মানের সর্বাধিক

• যদি নোডের মান জোড় হয়, তাহলে

  • ans :=সর্বাধিক উত্তর এবং (leftCnt + rightCnt + 1)

  • প্রত্যাবর্তন (leftCnt, rightCnt)

• অন্যথায়,

  • উত্তর :=সর্বাধিক উত্তর, leftCnt এবং rightCnt

  • ফেরত (-1, -1)

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• খুঁজুন(রুট)

• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class TreeNode:
   def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      ans = 0
      def find(node):
         nonlocal ans
         if not node:
            return -1, -1
         leftCnt = max(find(node.left)) + 1
         rightCnt = max(find(node.right)) + 1
         if node.val % 2 == 0:
            ans = max(ans, leftCnt + rightCnt + 1)
            return leftCnt, rightCnt
         else:
            ans = max(ans, max(leftCnt, rightCnt))
            return -1, -1
      find(root)
      return ans
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

ইনপুট

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

আউটপুট

5