পাইথনে বাইনারি ট্রি-এ জোড় যোগফলযুক্ত সর্বোচ্চ দৈর্ঘ্যের পাথ খুঁজে বের করার প্রোগ্রাম

একটি বাইনারি ট্রি দেওয়া আছে। আমাদের এমন একটি পাথ খুঁজে বের করতে হবে যাতে পাথে উপস্থিত নোড ভ্যালুগুলোর যোগফল জোড় (even) হয় এবং পাথটির দৈর্ঘ্য (নোড সংখ্যা) সর্বোচ্চ হয়।

উদাহরণস্বরূপ, নিচের ট্রির জন্য আউটপুট ৫:

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

পাথ: [5, 2, 4, 8, 5] → যোগফল ২৪ (জোড়), দৈর্ঘ্য ৫।

সমাধানের পদ্ধতি (DFS + DP on Tree)

প্রতিটি নোডের জন্য দুটি মান রিটার্ন করি:

even_len: এই নোড থেকে নিচে যাওয়া পাথে জোড় যোগফলের সর্বোচ্চ দৈর্ঘ্য।
odd_len: এই নোড থেকে নিচে যাওয়া পাথে বিজোড় যোগফলের সর্বোচ্চ দৈর্ঘ্য।

নোডের ভ্যালু যদি বিজোড় হয়, তবে জোড়+বিজোড় প্যারের যোগফল জোড় হয়। তাই বাম-ডানের even এবং odd কে ক্রস-কম্বাইন করি। নোডের ভ্যালু জোড় হলে জোড়+জোড় এবং বিজোড়+বিজোড় কম্বাইন করি। গ্লোবাল ans আপডেট করি।

পাইথন কোড উদাহরণ

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.val = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root):
        def dfs(node):
            if not node:
                return 0, float("-inf")
            left_0, left_1 = dfs(node.left)
            right_0, right_1 = dfs(node.right)
            if node.val & 1:  # odd
                self.ans = max(self.ans, left_1 + right_0 + 1, left_0 + right_1 + 1)
                return max(left_1 + 1, right_1 + 1, 0), max(left_0 + 1, right_0 + 1)
            else:  # even
                self.ans = max(self.ans, left_0 + right_0 + 1, left_1 + right_1 + 1)
                return max(left_0 + 1, right_0 + 1, 0), max(left_1 + 1, right_1 + 1)
        self.ans = 0
        dfs(root)
        return self.ans

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

ইনপুট

root = TreeNode(2) ... (উপরের ট্রি)