পাইথনে বাইনারি ট্রির সর্বোচ্চ অল্টারনেটিং পথের দৈর্ঘ্য বের করার প্রোগ্রাম

একটি বাইনারি ট্রি দেওয়া আছে। বাম-ডান অল্টারনেট করে নিচে যাওয়া সবচেয়ে লম্বা পথের দৈর্ঘ্য বের করুন।

উদাহরণ: ট্রি ছবিতে → আউটপুট ৫ (পথ [2,4,5,7,8])।

সমাধানের ধাপগুলো:

রিকার্সিভ DFS ফাংশন dfs(node, count, flag) লিখুন।
flag=True মানে বামে যাওয়া উচিত, False মানে ডানে।
প্রতিটি নোডে দুটি ডিরেকশন ট্রাই করুন এবং সর্বোচ্চ নিন।
রুট থেকে বাম ও ডান দুই দিকে কল করুন।

উদাহরণ

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)