পাইথনে বাইনারি ট্রিতে k-দৈর্ঘ্যের পথের সংখ্যা খুঁজে বের করার প্রোগ্রাম

মনে করুন একটি বাইনারি ট্রি আছে যেটিতে ইউনিক মান আছে এবং k একটি মান। ট্রিতে k-দৈর্ঘ্যের ইউনিক পথের সংখ্যা খুঁজে বের করতে হবে। পথ প্যারেন্ট-টু-চাইল্ড বা চাইল্ড-টু-প্যারেন্ট হতে পারে। দুটি পথ ভিন্ন হবে যদি কোনো নোড একটিতে থাকে অন্যটিতে না থাকে।

ইনপুট ট্রি এবং k=3 হলে আউটপুট ৪, পথগুলো: [12,8,3], [12,8,10], [8,12,15], [3,8,10]।

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

dfs() ফাংশন সংজ্ঞায়িত করুন যা node নেয়
- যদি node null হয়, [1] + [0]*(K-1) ফেরত দিন
- left := dfs(node.left)
- right := dfs(node.right)
- i = 0 থেকে K-1 পর্যন্ত, ans += left[i] * right[K-1-i]
- res := K আকারের 0 দিয়ে তালিকা
- res[0] = res[1] = 1
- i = 1 থেকে K-2 পর্যন্ত, res[i+1] += left[i] + right[i]
- res ফেরত দিন
মূল মেথড থেকে: ans := 0, dfs(root), ans ফেরত দিন

উদাহরণ

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, K):
        def dfs(node):
            if not node:
                return [1] + [0] * (K-1)
            left = dfs(node.left)
            right = dfs(node.right)
            for i in range(K):
                self.ans += left[i] * right[K - 1 - i]
            res = [0] * K
            res[0] = res[1] = 1
            for i in range(1, K - 1):
                res[i + 1] += left[i]
                res[i + 1] += right[i]
            return res
        self.ans = 0
        dfs(root)
        return self.ans

ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root, 3))

ইনপুট

root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10) 3