পাইথনে একটি গাছের অ-সংলগ্ন নোডের সর্বাধিক যোগফল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ট্রি আছে, আমাদেরকে প্রাপ্ত মানগুলির সর্বাধিক যোগফল খুঁজে বের করতে হবে যদি কোন দুটি মান সন্তানের অভিভাবক সংলগ্ন হতে পারে না৷

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

তাহলে আউটপুট 17 হবে কারণ 10, 4, 3 একে অপরের সংলগ্ন নয়।

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

একটি ফাংশন সংজ্ঞায়িত করুন f()। এটি নোড গ্রহণ করবে
যদি নোড নাল হয়, তাহলে
- রিটার্ন (0, 0)
(a, b) :=f(নোডের বামে)
(c, d) :=f(নোডের ডানদিকে)
একটি জোড়া ফেরত দিন (নোড + b + d এবং a + c, a + c-এর সর্বাধিক মান)
প্রধান পদ্ধতি থেকে f(root) কল করুন এবং এর প্রথম মান ফেরত দিন

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

উদাহরণ

class TreeNode:
def __init__(self, data, left = None, right = None):
   self.val = data
   self.left = left
   self.right = right
def f(node):
   if not node:
      return 0, 0
   a, b = f(node.left)
   c, d = f(node.right)
   return max(node.val + b + d, a + c), a + c
class Solution:
   def solve(self, root):
      return f(root)[0]
ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10) root.left.left = TreeNode(4) root.left.right = TreeNode(3) print(ob.solve(root))

ইনপুট

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10)
root.left.left = TreeNode(4)
root.left.right = TreeNode(3)