ধরুন আমাদের একটি বাইনারি গাছ আছে। আমাদের দীর্ঘতম পথের দৈর্ঘ্য খুঁজে বের করতে হবে যার যোগফল একটি জোড় সংখ্যা।
সুতরাং, যদি ইনপুটটি চিত্রের মতো হয়, তাহলে আউটপুট হবে 5, পাথ যেমন [5, 2, 4, 8, 5], যোগফল =24(এমনকি)।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড গ্রহণ করবে
- যদি নোড নাল হয়, তাহলে
- একটি জোড়া ফেরত দিন (0, -inf)
- (left_0, left_1) :=dfs(নোডের বামে)
- (right_0, right_1) :=dfs(নোডের ডানদিকে)
- নোডের মান যদি বিজোড় হয়, তাহলে
- উত্তর :=সর্বাধিক উত্তর, (বাম_1 + ডান_0 + 1) এবং (বাম_0 + ডান_1 + 1)
- একটি জোড়া ফেরত দিন (সর্বোচ্চ (বাম_1 + 1), (ডান_1 + 1) এবং 0), সর্বাধিক (বাম_0 + 1) এবং (ডান_0 + 1))
- অন্যথায়,
- উত্তর :=সর্বাধিক উত্তর, (বাম_০ + ডান_০ + ১) এবং (বাম_১ + ডান_১ + ১)
- একটি জোড়া ফেরত দিন (সর্বোচ্চ (বাম_0 + 1), (ডান_0 + 1), 0), সর্বাধিক (বাম_1 + 1), (ডান_1 + 1))
- প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
- উত্তর :=0
- dfs(root)
- উত্তর ফেরত দিন
উদাহরণ (পাইথন)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
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:
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:
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) 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
