पायथन में बाइनरी ट्री में सबसे लंबे सम-मूल्य पथ को खोजने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें ट्री में किन्हीं दो नोड्स के बीच केवल सम मान वाले नोड्स से बने सबसे लंबे पथ को ढूंढना है।

उदाहरण के लिए, यदि इनपुट निम्न ट्री है:

तो आउटपुट 5 होगा क्योंकि सबसे लंबा पथ [10, 2, 4, 8, 6] है।

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

ans := 0 आरंभ करें।
find() फ़ंक्शन परिभाषित करें जो node लेता है।
यदि node null है, तो (-1, -1) लौटाएं।
leftCnt := max(find(node.left)) + 1 और rightCnt := max(find(node.right)) + 1 की गणना करें।
यदि नोड का मान सम है, तो:
- ans := max(ans, leftCnt + rightCnt + 1) अपडेट करें।
- (leftCnt, rightCnt) लौटाएं।
अन्यथा:
- ans := max(ans, leftCnt, rightCnt) अपडेट करें।
- (-1, -1) लौटाएं।
मुख्य विधि से find(root) कॉल करें।
ans लौटाएं।

उदाहरण

class TreeNode:    def __init__(self, val, left=None, right=None):       self.val = val       self.left = left       self.right = right class Solution:    def solve(self, root):       ans = 0       def find(node):          nonlocal ans          if not node:             return -1, -1          leftCnt = max(find(node.left)) + 1          rightCnt = max(find(node.right)) + 1          if node.val % 2 == 0:             ans = max(ans, leftCnt + rightCnt + 1)             return leftCnt, rightCnt          else:             ans = max(ans, max(leftCnt, rightCnt))             return -1, -1       find(root)       return ans ob = Solution() root = TreeNode(2) root.left = TreeNode(10) root.right = TreeNode(4) root.right.left = TreeNode(8) root.right.right = TreeNode(2) root.right.left.left = TreeNode(6) print(ob.solve(root))

इनपुट

root = TreeNode(2) root.left = TreeNode(10) root.right = TreeNode(4) root.right.left = TreeNode(8) root.right.right = TreeNode(2) root.right.left.left = TreeNode(6)