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

ধরুন আমাদের একটি বাইনারি গাছ আছে, আমাদেরকে দীর্ঘতম পথটি খুঁজে বের করতে হবে যা বাম এবং ডান শিশু এবং নিচে যাওয়ার মধ্যে বিকল্প হয়।

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

তারপর আউটপুট হবে 5 কারণ বিকল্প পথ [2, 4, 5, 7, 8]।

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

যদি রুট নাল হয়, তাহলে
- রিটার্ন 0
একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড, গণনা, পতাকা গ্রহণ করবে
যদি নোড নাল না হয়, তাহলে
- যদি পতাকা True এর মত হয়, তাহলে
  - a :=dfs(নোডের বামে, গণনা + 1, মিথ্যা)
  - b :=dfs(নোডের ডানদিকে, 1, সত্য)
- অন্যথায় যখন পতাকা False এর মত হয়, তাহলে
  - a :=dfs(নোডের ডানদিকে, গণনা + 1, সত্য)
  - b :=dfs(নোডের বাম, 1, মিথ্যা)
- সর্বোচ্চ a, b ফেরত দিন
রিটার্ন গণনা
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
a :=dfs(মূলের বামে, 1, মিথ্যা)
b :=dfs(রুটের ডান, 1, সত্য)
সর্বোচ্চ a, b ফেরত দিন

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

উদাহরণ

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):
      if not root:
         return 0

      def dfs(node, count, flag):
         if node:
            if flag == True:
               a = dfs(node.left, count + 1, False)
               b = dfs(node.right, 1, True)
            elif flag == False:
               a = dfs(node.right, count + 1, True)
               b = dfs(node.left, 1, False)

            return max(a, b)
      return count

      a = dfs(root.left, 1, False)
      b = dfs(root.right, 1, True)

   return max(a, b)

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.right = TreeNode(7)
root.right.left.right.left = TreeNode(8)
print(ob.solve(root))

ইনপুট

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)root.right.left = TreeNode(5)
root.right.right = TreeNode(6)root.right.left.right = TreeNode(7)
root.right.left.right.left = TreeNode(8)