मान लीजिए कि हमारे पास एक बाइनरी ट्री है। हमें सबसे लंबे पथ की लंबाई ज्ञात करनी है जिसका योग एक सम संख्या है।
इसलिए, यदि इनपुट छवि की तरह है, तो आउटपुट 5 होगा, क्योंकि पथ [5, 2, 4, 8, 5], योग =24 (सम) जैसा है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक फ़ंक्शन को परिभाषित करें dfs() । यह नोड लेगा
- यदि नोड शून्य है, तो
- एक जोड़ी लौटाएं (0, -inf)
- (बाएं_0, बाएं_1):=dfs (नोड के बाएं)
- (दाएं_0, दाएं_1):=dfs(नोड के दाएं)
- यदि नोड का मान विषम है, तो
- उत्तर:=अधिकतम उत्तर, (बाएं_1 + दाएं_0 + 1) और (बाएं_0 + दाएं_1 + 1)
- एक जोड़ी लौटाएं (अधिकतम (बाएं_1 + 1), (दाएं_1 + 1) और 0) , अधिकतम (बाएं_0 + 1) और (दाएं_0 + 1))
- अन्यथा,
- उत्तर:=अधिकतम उत्तर, (बाएं_0 + दाएं_0 + 1) और (बाएं_1 + दाएं_1 + 1)
- एक जोड़ी लौटाएं (अधिकतम (बाएं_0 + 1), (दाएं_0 + 1), 0) , अधिकतम (बाएं_1 + 1), (दाएं_1 + 1))
- मुख्य विधि से निम्न कार्य करें -
- उत्तर:=0
- dfs(रूट)
- वापसी उत्तर
उदाहरण (पायथन)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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