পাইথনে বাইনারি ট্রিতে নোড এবং এর ডিসেন্ডেন্টের মধ্যে সর্বোচ্চ পার্থক্য বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি বাইনারি ট্রি আছে। আমাদের কাজ হল যেকোনো নোড এবং তার ডিসেন্ডেন্ট (বংশধর) নোডের মধ্যে সর্বোচ্চ পরম পার্থক্য (absolute difference) বের করা।

উদাহরণস্বরূপ, যদি ইনপুট ট্রিটি নিচের ছবির মতো হয়:

তবে আউটপুট হবে 7 কারণ নোড ৮ এবং ১ এর মধ্যে সর্বোচ্চ পরম পার্থক্য ৭।

• একটি dfs() ফাংশন ডিফাইন করুন যা node নেবে।
  • যদি node নাল না হয়, তবে [infinity, -infinity] রিটার্ন করুন।
  • left := dfs(node.left)
  • right := dfs(node.right)
  • res := [min(left[0], right[0], node.val), max(left[1], right[1], node.val)]
  • ans := max(ans, node.val - res[0], res[1] - node.val)
  • res রিটার্ন করুন।
• মূল মেথড থেকে:
  • ans := 0
  • dfs(root)
  • 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 [float("inf"), float("-inf")]
            left = dfs(node.left)
            right = dfs(node.right)
            res = [min(left[0], right[0], node.val), max(left[1], right[1], node.val)]
            self.ans = max(self.ans, node.val - res[0], res[1] - node.val)
            return res
        self.ans = 0
        dfs(root)
        return self.ans

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

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

7