पायथन में सम योग वाले सबसे लंबे पथ की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें उस सबसे लंबे पथ की लंबाई ढूंढनी है जिसका योग एक सम संख्या हो।

उदाहरण के लिए, यदि इनपुट ट्री है, तो आउटपुट 5 होगा, क्योंकि पथ [5, 2, 4, 8, 5] है, योग = 24 (सम)।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम DFS का उपयोग करेंगे जो प्रत्येक नोड के लिए दो मान लौटाता है: सम लंबाई और विषम लंबाई:

dfs(node) फंक्शन परिभाषित करें:
- यदि node null है, तो (0, -inf) लौटाएं
- (left_0, left_1) := dfs(node.left)
- (right_0, right_1) := dfs(node.right)
- यदि node.val विषम है:
  - ans := max(ans, left_1 + right_0 + 1, left_0 + right_1 + 1)
  - लौटाएं (max(left_1 + 1, right_1 + 1, 0), max(left_0 + 1, right_0 + 1))
- अन्यथा (सम मान):
  - ans := max(ans, left_0 + right_0 + 1, left_1 + right_1 + 1)
  - लौटाएं (max(left_0 + 1, right_0 + 1, 0), max(left_1 + 1, right_1 + 1))
मुख्य मेथड में 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 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)