পাইথনে বাইনারি ট্রিতে জোড় মান সম্বলিত সর্বোচ্চ পথ খুঁজে বের করার প্রোগ্রাম

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

ইনপুট ট্রি হলে আউটপুট হবে 5, কারণ সর্বোচ্চ পথ হল [10, 2, 4, 8, 6]।

সমাধানের ধাপসমূহ

ans := 0
find() ফাংশন সংজ্ঞায়িত করুন যা node নেয়।
যদি node null হয়, তবে (-1, -1) ফেরত দিন।
leftCnt := max(find(node.left)) + 1
rightCnt := max(find(node.right)) + 1
যদি node.val জোড় হয়, তবে ans := max(ans, leftCnt + rightCnt + 1) এবং (leftCnt, rightCnt) ফেরত দিন।
অন্যথায়, ans := max(ans, leftCnt, rightCnt) এবং (-1, -1) ফেরত দিন।
মূল মেথড থেকে find(root) কল করুন এবং ans ফেরত দিন।

উদাহরণ কোড

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)